在给定的二进制字符串中最大化具有相同 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) 的空间复杂度，这意味着当前方法效率不高。

哈希表方法

在这种方法中，我们将使用哈希表来降低时间复杂度。让我们首先了解基本思想 -

这种方法背后的基本思想是，如果任何前缀具有相同比例的零和一，那么我们继续在字符串中移动，并在任何索引处再次获得相同的比例，那么我们可以在那里进行分区。由于我们正在考虑整个字符串与完整字符串的比例，因此它将是一个前缀，因为我们必须在那里结束。

步骤

首先，我们将创建一个哈希表，其中键为整数对，值为整数。然后，我们将遍历字符串并维护两个变量来计算零和一的数量。

我们将找到数字的最大公约数，并将其除以它以存储表示比率的两个数字的最简形式。

将比率存储为对的形式，并将当前对的数量增加。

我们将维护一个整数来存储答案，并将使用每次迭代更新它，对于最后一次迭代或索引，它将是最终答案。

示例

Open Compiler
#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 个不同的对。

注意 我们在哈希表方法中看到，最后一个比率将是问题的答案。这导致了一种新的方法，与哈希表相比，它在时间和空间复杂度方面都更有效。

我们可以遍历字符串并找到零和一的总数，然后获取它们的计数和比率。

再次，我们将遍历字符串并计算零和一。在每个索引处，我们将检查比率，如果比率等于最终比率，那么我们可以将其标记为分区。

这将为我们提供最佳技术，线性时间复杂度用于搜索，但对于最大公约数有额外的对数因子，并且空间复杂度为常数。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

在本教程中，我们实现了三种方法来找到可以基于特定子字符串中零与一数量的相同比率进行的最大分区数。我们讨论了三种方法，一种是找到所有可能的分割，这是最差的方法，另一种是使用哈希表找到总比率，并在发生时计算分割。

更新于: 2023年5月17日

110 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告