二進位制字串任意旋轉後開頭和結尾連續放置的 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)。