二进制字符串任意旋转后开头和结尾连续放置的 0 的最大数量

---

二进制字符串表示该字符串仅包含两种字符，要么是 1 要么是 0。它被称为二进制。在这个问题中，我们给定了一个二进制字符串 str 以及字符串的大小 'n'。我们的任务是找到二进制字符串任意旋转后开头和结尾连续放置的 0 的最大数量。让我们看看下面的示例和解释，以便更好地理解这个问题。

示例

输入 1

str = “101001, n = 6

输出 1

2

解释

字符串可以以以下任何可能的方式旋转

"101001"，字符串开头的 0 的数量为 0，结尾的 0 的数量为 0。总计 = 0+0 = 0

"110100"，字符串开头的 0 的数量为 0，结尾的 0 的数量为 2。总计 = 0+2 = 2

"011010"，字符串开头的 0 的数量为 1，结尾的 0 的数量为 1。总计 = 1+1 = 2

"001101"，字符串开头的 0 的数量为 2，结尾的 0 的数量为 0。总计 = 2+0 = 2

"100110"，字符串开头的 0 的数量为 0，结尾的 0 的数量为 1。总计 = 0+1 = 1

"010011"，字符串开头的 0 的数量为 1，结尾的 0 的数量为 0。总计 = 1+0 = 1

由于最大的可能的 0 的数量是 2。

输入 2

str = “1100”, k = 4

输出 2

2

方法

我们已经看到了上面给定大小为 n 的字符串的示例，让我们转向方法

方法 1：朴素方法

概念很简单，生成给定字符串的所有可能的旋转，并检查每个字符串，计算字符串开头和结尾连续放置的 0 的数量。在变量 'cnt' 中维护 0 的最大计数，并返回该计数。

示例

让我们看看下面的代码，以便更好地理解上述方法。

#include <bits/stdc++.h>
using namespace std;
// Create a function to count maximum consecutive 0's at  the beginning and ending in any rotation of binary string
int maxZeros(string str, int n){
   // Verify that the string contains only 0s as characters.
   int cnt = 0;
   // traverse the string to check all the char of the string are 0's or not
   for (int i = 0; i < n; i++) {
      if (str[i] == '0')
         cnt++;
   }
   // check the count of 0's equal to the size of the string
   if (cnt == n) {
      return cnt;
   }
   string sstr = str + str; //extended string with itself
   cnt = 0; //reset the count equal to 0
   // Create all possible string rotations.
   for (int i = 0; i < n; i++) {
      int cnts = 0; //0's at start
      int cnte = 0; //0's at end
      // for the beginning zeroes 
       for (int j = i; j < i + n; ++j) {
          if (sstr[j]=='0')
             cnts++;
          else
             break;
       } 
       // for the ending zeroes
       for (int j = i + n - 1; j >= i; j--) {
          if (sstr[j]=='0')
             cnte++;
          else
             break;
       } 
       // get maximum 0's
       cnt = max(cnt, cnts+cnte);
   }   
   // return maximum cout of the 0's
      return cnt;
} 
int main(){
   string str = "101001"; // given string
   cout << "Input String: " << str << endl;
   int n = 6; //size of the string 
   int maxZerosCount = maxZeros(str, n);    
   cout << "Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String: ";
   cout<<maxZerosCount; // Print maximum cout of the 0's
   return 0;
}
    

输出

Input String: 101001
Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String: 2

时间和空间复杂度

时间复杂度为 O(N^2)。空间复杂度为 O(N)。这里 N 是字符串的大小

方法 2：连续的零

思路很简单，计算给定字符串的连续零，并计算字符串开头和结尾连续放置的零。在变量 'cnt' 中维护 0 的最大计数，并返回该计数。

示例

让我们看看下面的代码，以便更好地理解上述方法。

#include <bits/stdc++.h>
using namespace std; 
// Create a function to count maximum consecutive 0's at the beginning and ending in any rotation of binary string
int maxZeros(string str, int n){
   // Verify that the string contains only 0s as characters.
   int cnt = 0;    
   // Traverse string to check if all the chars of the string are 0's or not
   for (int i = 0; i < n; i++) {
      if (str[i]=='0')
         cnt++;
   } 
   // check the count of 0's equal to the size of the string
   if (cnt == n) {
       return cnt;
   }
   cnt = 0; //reset the count equal to 0 
   int tempcnt = 0; 
   for (int i = 0; i < n; i++) {
      if (str[i]=='0')
         tempcnt++;
      else {
         cnt = max(cnt, tempcnt);
         tempcnt = 0;
      }
   } 
    // get maximum count 
    cnt = max(cnt, tempcnt);
    // For 0's present at the end and 
    // beginning of the string
    int s = 0, e = n - 1;
    tempcnt = 0; 
    // for start
    while (str[s] != '1' && s < n) {
       tempcnt++;
       s++;
    }
    // for end
    while (str[e] != '1' && e >= 0) {
       tempcnt++;
       e--;
    } 
    // get maximum 0's
    cnt = max(cnt, tempcnt);
    // return maximum cout of the 0's
    return cnt; 
 } 
 int main(){
    string str = "101001"; // given string
    cout << "Input String: " << str << endl;
    int n = 6; //size of the string
    int maxZerosCount = maxZeros(str, n);
    cout << "Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String: ";
    cout<<maxZerosCount; // print maximum cout of the 0's 
    return 0;
}

输出

Input String: 101001
Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String: 2

时间和空间复杂度

时间复杂度：O(N)，其中 N 是字符串的大小。空间复杂度：O(1)

结论

在本教程中，我们实现了一个程序来查找二进制字符串任意旋转后开头和结尾连续放置的 0 的最大数量。我们实现了两种方法：朴素方法和高效方法。朴素方法的时间复杂度为 O(N^2)，空间复杂度为 O(N)。高效方法的时间复杂度为 O(N)，空间复杂度为 O(1)。