C++ 给定字符串的最长子字符串，不超过X个0和Y个1

子字符串是从给定字符串中连续的字符序列，可以通过从子字符串的前部和后部删除一些字符（可能是全部或无）来获得。我们给定一个二进制字符串，我们必须找到包含最多X个0和Y个1的最长子字符串的长度，其中X和Y是给定的输入。

示例

输入1

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

解释

从第一个索引开始，长度为3的子字符串”010″是满足条件的最长子字符串。

输入2

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

获取所有子字符串

在这个方法中，我们将获取所有的子字符串，然后统计其中的零和一的数量。如果零或者一的数量大于给定的限制，则将移动到下一个子字符串，否则将比较答案与当前子字符串的大小，并进行更新。

我们将使用嵌套的循环来获取特定长度的子字符串。对于每个长度，我们将从第一个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)的代码。