给定字符串中最多包含 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)。