給定字串中最多包含 X 個 0 和 Y 個 1 的最長子字串

---

子字串是從給定字串中連續的字元序列，可以透過移除子字串的前端和後端的一些字元（可能全部或沒有）來獲得。我們給定一個二進位制字串，我們需要找到包含最多 X 個零和 Y 個一的子字串的最長長度，其中 X 和 Y 是給定的輸入。

示例

輸入

string str = "101011";
int x = 1; 
int y = 2;

輸出

The length of the longest substring with at most X zeroes and Y ones is 3

解釋

從索引 1 開始長度為 3 的子字串“010”是在給定條件下最長的子字串。

輸入

string str = "101011100011";
int x = 3; 
int y = 2;

輸出

The length of the longest substring with at most X zeroes and Y ones is 5

獲取所有子字串

在這種方法中，我們將獲取所有子字串，然後計算其中存在的零和一的數量。如果零或一的數量大於給定的限制，我們將轉到下一個子字串，否則將答案與當前子字串的大小進行比較並更新它。

我們將使用巢狀的 for 迴圈來獲取特定長度的子字串。對於每個長度，我們將從第一個索引 0 開始，然後將移動直到達到字串的總長度減去當前子字串長度的索引。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get all the length of the required substring 
int getLen(string str, int x, int y){
   // getting length of the given string 
   int len = str.size();
   int ans = 0; // variable to store the answer  
   // traversing over the string size wise
   for(int size = 1; size <= len; size++){
      for(int start = 0; start <= len-size; start++){
         int end = start + size; 
         int countOnes = 0, countZeroes = 0;            
         // traversing over the current substring 
         for(int i = start; i < end; i++){
            if(str[i] == '1'){
               countOnes++;
            } else {
               countZeroes++;
            }
         }            
         if(countOnes <= x && countZeroes <= y){
            ans = max(ans, size);
         }
      }
   }
   return ans; // return the final answer 
}
int main(){
   string str = "101011";
   int x = 1; 
   int y = 2; 
   // calling the function 
   cout<<"The length of the longest substring with at most X zeroes and Y ones is: "<<getLen(str, x, y)<<endl;
   return 0; 
}

輸出

The length of the longest substring with at most X zeroes and Y ones is: 3

時間和空間複雜度

上述程式碼的時間複雜度為 O(N^3)，其中 N 是給定字串的大小。我們使用了三個巢狀的 for 迴圈，使時間複雜度達到 3 的冪。

上述程式碼的空間複雜度為常數或 O(1)，因為我們在這裡沒有使用任何額外的空間。

雙指標方法

在這種方法中，我們將使用雙指標方法以線性時間複雜度獲取結果。

我們將建立一個函式並獲取一個慢指標和一個快指標，快指標將移動並獲取當前索引是“1”或“0”，並更新相應的計數。

如果任何字元的計數大於給定的最大值，則必須將慢指標移動到下一個位置並獲取所需的答案。

在主函式中，我們將呼叫該函式並列印所需的值。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get all the length of the required substring 
int getLen(string str, int x, int y){
   // getting length of the given string 
   int len = str.size();
   int ans = 0; // variable to store the answer    
   // pointers to traverse over the given string 
   int slow = 0, fast = 0;
   int zeroes = 0, ones = 0;     
   while(fast < len){
      if(str[fast] == '1'){
         ones++;
      } else {
         zeroes++;
      }        
      if(ones > x || y < zeroes){
         if(str[slow] == '1'){
            ones--;
         } else {
            zeroes--;
         }
         slow++;
      }
      fast++;
      // updating answer 
      ans = max(ans, fast - slow);
   }
   return ans; // return the final answer 
}
int main(){
   string str = "10101";
   int x = 1; 
   int y = 2; 
   cout<<"The length of the longest substring with at most X zeroes and Y ones is: "<<getLen(str, x, y)<<endl;
   return 0; 
}

輸出

The length of the longest substring with at most X zeroes and Y ones is: 3

時間和空間複雜度

上述程式碼的時間複雜度為線性或 O(N)，其中 N 是給定字串的大小。

上述程式碼的空間複雜度為常數或 O(1)，因為我們在這裡沒有使用任何額外的空間。

結論

在本教程中，我們實現了一個程式碼來查詢最多包含 X 個零和 Y 個一的子字串的最長長度。子字串是從給定字串中連續的字元序列，可以透過移除子字串的前端和後端的一些字元來獲得。我們實現了兩個程式碼，其時間複雜度分別為 O(N^3) 和 O(N)。