C++ 寻找大小不超过3N的二进制字符串，其中至少包含两个大小为2N的给定字符串作为子序列

给定三个长度相等的字符串，长度为2N，其中N是一个整数。我们必须创建一个大小为3N的字符串，并且至少有两个给定字符串是其子序列。此外，给定字符串是二进制字符串，意味着它们只包含两个不同的字符’0’和’1’。我们将通过遍历字符串并获取0和1的频率来实现一段代码。

样例

输入

string str1 = “11”;
string str2 = “10”;
string str3 = “10”; 

输出结果

110

解释 : 前两个字符串是给定输出字符串的顺序。

输入

string str1 = “001111”;
string str2 = “001111”;
string str3 = “11000”; 

输出

00001111

观察

在给定的问题中，我们有偶数长度的二进制字符串，这意味着只有两个不同的字符。在这里，我们只有两个字符，所以要么这两个字符的频率都是N，要么其中一个字符的频率超过N，而另一个字符的频率小于N。

例如：如果字符串1中字符’0’的频率超过N，字符串2中字符’1’的频率也超过N。或者，另一种情况是它的相反情况，在这种情况下，字符串2中字符’0’的频率大于N，字符串1中字符’1’的频率大于N。现在，第三个字符串的频率要么是大于等于N的’1’，这使得它与其中一个字符串的’1’的频率相同，或者在’0’的情况下，它与给定字符串中的一个字符的’0’的频率相同。

因此，关键点是始终会存在两个字符串，其中任一字符的频率大于或等于N。因此，始终可以生成最终字符串。

方法

在这种方法中，我们将创建一个函数，用于检查所有三个给定字符串中字符1和字符0的频率。

对于任意两个具有相同较高频率字符的字符串，我们将取它们和具有最高频率的字符，并将它们传递给另一个函数来计算所需的字符串。

我们将使用双指针技术先获取所有较低频率的字符，然后再获取较高频率的字符。

示例

#include <bits/stdc++.h>
using namespace std;

// function to build the string 
string buildString(string str1, string str2, char req){
   // using the two pointers approach  
   int ptr1 = 0, ptr2 = 0;
   int len = str1.size();
   string ans = "";
   while(ptr1 < len && ptr2 < len){
      while(ptr1 < len && str1[ptr1] != req){
         ans += str1[ptr1];
         ptr1++;
      }
      while(ptr2 < len && str2[ptr2] != req){
         ans += str2[ptr2];
         ptr2++;
      }
      // if we are at end break
      if(ptr1 == len || ptr2 == len){
         break;
      }
      if(str1[ptr1] == str2[ptr2]){
         ans += str1[ptr1];
         ptr1++, ptr2++;
      } else{
         ans += str1[ptr1];
         ptr1++;
      }
   }
   // adding the remaining characters 
   while(ptr1 < len){
      ans += str1[ptr1];
      ptr1++;
   }
   while(ptr2 < len){
      ans += str2[ptr2];
   }
   return ans;
}
// function to get the string 
string getString(string str1, string str2, string str3){
   // getting length of the given strings as given the size of all the strings is same 
   int len = str1.size();
   // creating arrays to store the frequency of the zeroes
   int freq[3] = {0};
   // getting values for the first string
   for(int i=0; i<len; i++){
      if(str1[i] == '0'){
         freq[0]++;
      }
   }
   // getting values for the second string
   for(int i=0; i<len; i++){
      if(str2[i] == '0'){
         freq[1]++;
      }
   }
   // getting values for the third string
   for(int i=0; i<len; i++){
      if(str3[i] == '0'){
         freq[2]++;
      }
   }
   char req; 
   // conditions to make the combination of the two string 
   if((freq[0] >= len/ 2 && freq[1] >= len/2) || (freq[0] <= len/ 2 && freq[1] <= len/2) ){
      // frequency of zero or one is more for both first and second string leave the third string away 
      if(freq[0] >= len/2 && freq[1]>= len/2){
         req = '0';
      }
      else{
         req = '1';
      }
   }
   else if((freq[0] >= len/ 2 && freq[2] >= len/2) || (freq[0] <= len/ 2 && freq[2] <= len/2) ){
      // frequency of zero or one is more for both first and third string leave the second string away 
      str2 = str3;
      if(freq[0] >= len/2 && freq[2] >= len/2){
         req = '0';
      } else{
         req = '1';
      }
   } else{
      // both initial conditions are false means both second and third string have the frequency of zero or one in same side leave the first string away 
      str1 = str3;
      if(freq[2] >= len/2 && freq[1] >= len/2){
         req = '0';
      } else{
         req = '1';
      }
   }
   // calling function to return the requird string
   return buildString(str1, str2, req);
}
int main(){
   string str1 = "001111"; // given strings
   string str2 = "001111";
   string str3 = "001100";
   // getting the required string 
   cout<<"The required string of at most size 3*N is: " << getString(str1, str2, str3 )<<endl;
}

输出

The required string of at most size 3*N is: 00001111

时间和空间复杂度

以上代码的时间复杂度为O(N)，其中N是给定长度的大小，因为我们只遍历了一次字符串。

以上代码的空间复杂度为O(N)，用于存储最终的答案。

结论

在这个程序中，我们实现了一个代码来获得一个大小为3×N的字符串，它是给定的三个二进制字符串（长度为2×N）中任意两个字符串的超级序列。我们使用了鸽巢原理来证明答案总是存在，并通过使用两个指针和计数频率来创建所需的字符串，时间和空间复杂度为O(N)。