查找大小最多为 3N 的二进制字符串，其中包含至少 2 个大小为 2N 的给定字符串作为子序列
我们给出了三个大小相等的字符串，它们等于 2*N，其中 N 是整数。我们必须创建一个大小为 3*N 的字符串，并且至少有两个给定字符串中的字符串作为它的子序列。此外，给定的字符串是二进制字符串，这意味着它们只包含两个不同的字符"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。现在，第三个字符串的频率"1"大于或等于 N，这使得它与其中一个字符串共享相同的频率"1"，或者在"0"的情况下，它也与给定字符串之一共享相同的频率"0"。
因此，关键是总会有两个字符串存在，任何一个字符的频率大于或等于 N。因此，最终的字符串总是可以制作的。
方法
在这种方法中，我们将创建一个函数，在该函数中我们将检查所有三个给定字符串中 1 和 0 的频率。
对于任何两个具有相同较高频率的任意字符的字符串，我们将获取它们和频率最高的字符，并将它们传递给另一个函数以计算所需的字符串。
我们将使用双指针技术首先获取所有频率较低的字符，然后获取频率较高的字符。
示例
#include <bits/stdc++.h>
using namespace std;
// 构建字符串的函数
string buildString(string str1, string str2, char req){
// 使用双指针方法
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++;
}
}
// 添加剩余的字符
while(ptr1 < len){
ans += str1[ptr1];
ptr1++;
}
while(ptr2 < len){
ans += str2[ptr2];
}
return ans;
}
// 获取字符串的函数
string getString(string str1, string str2, string str3){
// 获取给定字符串的长度，因为所有字符串的大小相同
int len = str1.size();
// 创建数组来存储零的频率
int freq[3] = {0};
// 获取第一个字符串的值
for(int i=0; i<len; i++){
if(str1[i] == '0'){
freq[0]++;
}
}
// 获取第二个字符串的值
for(int i=0; i<len; i++){
if(str2[i] == '0'){
freq[1]++;
}
}
// 获取第三个字符串的值
for(int i=0; i<len; i++){
if(str3[i] == '0'){
freq[2]++;
}
}
char req;
// 使两个字符串组合的条件
if((freq[0] >= len/ 2 && freq[1] >= len/2) || (freq[0] <= len/ 2 && freq[1] <= len/2) ){
// 第一和第二个字符串中零或一的频率都比较大，第三个字符串则远离
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) ){
// 第一弦和第三弦出现频率为零或一的次数较多，第二弦则略少
str2 = str3;
if(freq[0] >= len/2 && freq[2] >= len/2){
req = '0';
} else{
req = '1';
}
} else{
// 两个初始条件都是假的，意味着第二和第三弦在同一侧的频率为零或一，第一弦则远离
str1 = str3;
if(freq[2] >= len/2 && freq[1] >= len/2){
req = '0';
} else{
req = '1';
}
}
// 调用函数返回所需字符串
return buildString(str1, str2, req);
}
int main(){
string str1 = "001111"; // 给定字符串
string str2 = "001111";
string str3 = "001100";
// 获取所需字符串
cout<<"所需字符串的最大大小为 3*N：" << getString(str1, str2, str3 )<<endl;
}
输出
所需字符串的最大大小为 3*N：00001111
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定长度的大小，因为我们只移动字符串一次。
上述代码的空间复杂度为 O(N)，用于存储最终答案。
结论
在这个程序中，我们实现了一个代码来获取一个大小为 3*N 的字符串，它是给定的三个长度为 2*N 的二进制字符串中任意两个字符串的超序列。我们使用鸽巢原理来证明答案总是存在的，然后通过使用两个指针并计算频率，我们以 O(N) 的时间和空间复杂度创建了所需的字符串。
