在給定的二進位制字串中最大化具有相同 0 和 1 比例的分割

---

二進位制字串是指僅包含 0 和 1 作為不同字元型別的字串。我們給定一個二進位制字串，任務是將其分成若干個分割槽（可能為零），其中每個分割槽都包含相等比例的 0 和 1。我們將使用雜湊表來解決問題，並具有高效的時間和空間複雜度。

示例

輸入 1

字串 str = 100010001

輸出: 3

解釋 給定的字串可以分成三個子字串，這些子字串將包含相同比例的零和一。我們可以將字串分成範圍 [0,2]、[3,5] 和 [6,8]，它們都具有 2:1 的零和一的比例。

輸入 2

字串 str = 01000111

輸出: 2

解釋 給定的字串可以分成兩個子字串，第一個在範圍 [0,1]，第二個在範圍 [2,7]。這兩個區域都將包含相同的 1:1 比例。

樸素方法

在這種方法中，我們可以找到對子字串進行分割的所有方法，然後檢查哪些方法包含相同比例的零和一。

這種方法的問題在於時間複雜度，生成字串的所有分割將花費 2^N 步，因此僅對於分割的時間複雜度為 O(2^N)，然後檢查比例將存在 N 的一個因子。

此外，為了生成所有分割，我們使用遞迴，這將花費 O(N) 的空間複雜度，這意味著當前方法效率不高。

雜湊表方法

在這種方法中，我們將使用雜湊表來降低時間複雜度。讓我們首先了解基本思想 -

這種方法背後的基本思想是，如果任何字首具有相同比例的零和一，那麼我們繼續在字串中移動，並在任何索引處再次獲得相同的比例，那麼我們可以在那裡進行分割槽。由於我們正在考慮整個字串與完整字串的比例，因此它將是一個字首，因為我們必須在那裡結束。

步驟

首先，我們將建立一個雜湊表，其中鍵為整數對，值為整數。然後，我們將遍歷字串並維護兩個變數來計算零和一的數量。

我們將找到數字的最大公約數，並將其除以它以儲存表示比率的兩個數字的最簡形式。

將比率儲存為對的形式，並將當前對的數量增加。

我們將維護一個整數來儲存答案，並將使用每次迭代更新它，對於最後一次迭代或索引，它將是最終答案。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the solution 
int maxPart(string str){
   int len = str.length(); // variable to find the length of the string 
   int ans = 0; // variable to store the answer
   map<pair<int,int>,int>mp; // defining hashmap    
   // variable to maintain the count of zeros and ones 
   int zcount = 0, ocount = 0;    
   // traversing over the string 
   for(int i=0; i<len; i++){
      if(str[i] == '0'){
         zcount++;
      }
      else{
         ocount++;
      }        
      // getting gcd
      int gcd = __gcd(zcount,ocount);        
      // dividing by gcd to get the ratio 
      int first = zcount/gcd;
      int second = ocount/gcd;        
      // adding values to hashmap 
      mp[{first,second}]++;
      ans = mp[{first,second}];
   }
   return ans;
}
int main(){
   string str = "100010001"; // given string     
   // calling the function to get the maximum number of partitions for the ratio
   cout<<"The maximize partitions in the given Binary String having the same ratio of 0s and 1s is "<<maxPart(str)<<endl;
   return 0;
}

輸出

The maximize partitions in the given Binary String having the same ratio of 0s and 1s is 3

時間和空間複雜度

上述程式碼的時間複雜度為 O(N*log(N))，其中 N 是給定陣列的大小。我們將元素儲存在雜湊表中，這給我們帶來了額外的對數時間因子。

上述程式碼的空間複雜度為 O(N)，這是由於雜湊表，因為可能存在 N 個不同的對。

注意 我們在雜湊表方法中看到，最後一個比率將是問題的答案。這導致了一種新的方法，與雜湊表相比，它在時間和空間複雜度方面都更有效。

我們可以遍歷字串並找到零和一的總數，然後獲取它們的計數和比率。

再次，我們將遍歷字串並計算零和一。在每個索引處，我們將檢查比率，如果比率等於最終比率，那麼我們可以將其標記為分割槽。

這將為我們提供最佳技術，線性時間複雜度用於搜尋，但對於最大公約數有額外的對數因子，並且空間複雜度為常數。

結論

在本教程中，我們實現了三種方法來找到可以基於特定子字串中零與一數量的相同比率進行的最大分割槽數。我們討論了三種方法，一種是找到所有可能的分割，這是最差的方法，另一種是使用雜湊表找到總比率，並在發生時計算分割。