Find Binary String of size at most 3N containing at least 2 given strings of size 2N as subsequences
Given three binary strings a, b, and c each having 2*N characters each, the task is to find a string having almost 3*N characters such that at least two of the given three strings occur as its one of the subsequence.
Examples:
Input: a = β00β, b = β11β, c = β01β
Output: β010β
Explanation: The strings β00β and β01β are subsequences of string β010β and is has not more than 3*N characters. Also, β001β, β011β can be the possible answers.Input: a = β011001β, b = β111010β, c = β010001β
Output: β011001010β³
Explanation: Here, all the three given strings occur as the subsequences of the output string.
Approach: The given problem can be solved using the following observations:
- It can be observed that according to the Pigeonhole Principle, there must exist a set of two strings such that the most frequent character in both the strings is the same and its frequency is >=N.
- Hence, for two such strings, a string of N most frequent characters can be created. The other remaining N characters of both the strings can be appended into the string respectively according to the order they occur. Therefore, the maximum size of the resultant string will be at most 3*N.
Therefore, after finding the set of strings with the same most frequent element, the rest can be solved using the two-pointer approach. Maintain two pointers, one for each string, and follow the below steps:
- Initially, i =0 and j = 0, where i represent the 1st string s1 and j represent the second string s2.
- If s1[i] is not equal to the most frequent character, print s1[i] and increment i.
- If s2[j] is not equal to the most frequent character, print s2[i] and increment j.
- If both s1[i] and s2[j] is representing the most frequent character, print s1[i] and increment both i and j.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find most frequent // character in the given string char MostFrequent(string s) { // Stores the frequency of // 0 and 1 respectively int arr[] = { 0, 0 }; for ( char ch : s) { arr[ch - '0' ]++; } // Stores most frequent character char result = arr[0] > arr[1] ? '0' : '1' ; // Return Answer return result; } // Function to find a Binary String of // at most 3N characters having at least // two of the given three strings of 2N // characters as one of its subsequence void findStr(string& a, string& b, string& c) { // Stores most frequent char char freq; // Stores the respective string // with most frequent values string s1, s2; // Code to find the set of // two strings with same // most frequent characters if (MostFrequent(a) == MostFrequent(b)) { s1 = a; s2 = b; freq = MostFrequent(a); } else if (MostFrequent(a) == MostFrequent(c)) { s1 = a; s2 = c; freq = MostFrequent(a); } else { s1 = b; s2 = c; freq = MostFrequent(b); } // Pointer to iterate strings int i = 0, j = 0; // Traversal using the // two-pointer approach while (i < s1.size() && j < s2.size()) { // if current character // is not most frequent while (i < s1.size() && s1[i] != freq) { cout << s1[i++]; } // if current character // is not most frequent while (j < s2.size() && s2[j] != freq) { cout << s2[j++]; } // If end of string is reached if (i == s1.size() || j == s2.size()) break ; // If both string character // are same as most frequent if (s1[i] == s2[j]) { cout << s1[i]; i++; j++; } else { cout << s1[i]; i++; } } // Print leftover characters // of the string s1 while (i < s1.size()) { cout << s1[i++]; } // Print leftover characters // of the string s2 while (j < s2.size()) { cout << s2[j++]; } } // Driver Code int main() { string a, b, c; a = "00" ; b = "11" ; c = "01" ; findStr(a, b, c); return 0; } |
Java
// Java program for the above approach class GFG { // Function to find most frequent // character in the given String static char MostFrequent(String s) { // Stores the frequency of // 0 and 1 respectively int []arr = { 0 , 0 }; for ( char ch : s.toCharArray()) { arr[ch - '0' ]++; } // Stores most frequent character char result = arr[ 0 ] > arr[ 1 ] ? '0' : '1' ; // Return Answer return result; } // Function to find a Binary String of // at most 3N characters having at least // two of the given three Strings of 2N // characters as one of its subsequence static void findStr(String a, String b, String c) { // Stores most frequent char char freq; // Stores the respective String // with most frequent values String s1 = "" , s2 = "" ; // Code to find the set of // two Strings with same // most frequent characters if (MostFrequent(a) == MostFrequent(b)) { s1 = a; s2 = b; freq = MostFrequent(a); } else if (MostFrequent(a) == MostFrequent(c)) { s1 = a; s2 = c; freq = MostFrequent(a); } else { s1 = b; s2 = c; freq = MostFrequent(b); } // Pointer to iterate Strings int i = 0 , j = 0 ; // Traversal using the // two-pointer approach while (i < s1.length()&& j < s2.length()) { // if current character // is not most frequent while (i < s1.length() && s1.charAt(i) != freq) { System.out.print(s1.charAt(i++)); } // if current character // is not most frequent while (j < s2.length() && s2.charAt(j) != freq) { System.out.print(s2.charAt(j++)); } // If end of String is reached if (i == s1.length()|| j == s2.length()) break ; // If both String character // are same as most frequent if (s1.charAt(i) == s2.charAt(j)) { System.out.print(s1.charAt(i)); i++; j++; } else { System.out.print(s1.charAt(i)); i++; } } // Print leftover characters // of the String s1 while (i < s1.length()) { System.out.print(s1.charAt(i++)); } // Print leftover characters // of the String s2 while (j < s2.length()) { System.out.print(s2.charAt(j++)); } } // Driver Code public static void main(String args[]) { String a = "00" ; String b = "11" ; String c = "01" ; findStr(a, b, c); } } // This code is contributed Saurabh Jaiswal |
C#
// C# program for the above approach using System; class GFG { // Function to find most frequent // character in the given string static char MostFrequent( string s) { // Stores the frequency of // 0 and 1 respectively int []arr = { 0, 0 }; foreach ( char ch in s) { arr[ch - '0' ]++; } // Stores most frequent character char result = arr[0] > arr[1] ? '0' : '1' ; // Return Answer return result; } // Function to find a Binary String of // at most 3N characters having at least // two of the given three strings of 2N // characters as one of its subsequence static void findStr( string a, string b, string c) { // Stores most frequent char char freq; // Stores the respective string // with most frequent values string s1 = "" , s2 = "" ; // Code to find the set of // two strings with same // most frequent characters if (MostFrequent(a) == MostFrequent(b)) { s1 = a; s2 = b; freq = MostFrequent(a); } else if (MostFrequent(a) == MostFrequent(c)) { s1 = a; s2 = c; freq = MostFrequent(a); } else { s1 = b; s2 = c; freq = MostFrequent(b); } // Pointer to iterate strings int i = 0, j = 0; // Traversal using the // two-pointer approach while (i < s1.Length && j < s2.Length) { // if current character // is not most frequent while (i < s1.Length && s1[i] != freq) { Console.Write(s1[i++]); } // if current character // is not most frequent while (j < s2.Length && s2[j] != freq) { Console.Write(s2[j++]); } // If end of string is reached if (i == s1.Length || j == s2.Length) break ; // If both string character // are same as most frequent if (s1[i] == s2[j]) { Console.Write(s1[i]); i++; j++; } else { Console.Write(s1[i]); i++; } } // Print leftover characters // of the string s1 while (i < s1.Length) { Console.Write(s1[i++]); } // Print leftover characters // of the string s2 while (j < s2.Length) { Console.Write(s2[j++]); } } // Driver Code public static void Main() { string a = "00" ; string b = "11" ; string c = "01" ; findStr(a, b, c); } } // This code is contributed Samim Hossain Mondal. |
Python3
# python3 program for the above approach # Function to find most frequent # character in the given string def MostFrequent(s): # Stores the frequency of # 0 and 1 respectively arr = [ 0 , 0 ] for ch in s: arr[ ord (ch) - ord ( '0' )] + = 1 # Stores most frequent character result = '0' if arr[ 0 ] > arr[ 1 ] else '1' # Return Answer return result # Function to find a Binary String of # at most 3N characters having at least # two of the given three strings of 2N # characters as one of its subsequence def findStr(a, b, c): # Stores most frequent char freq = '' # Stores the respective string # with most frequent values s1, s2 = " ", " " # Code to find the set of # two strings with same # most frequent characters if (MostFrequent(a) = = MostFrequent(b)): s1 = a s2 = b freq = MostFrequent(a) elif (MostFrequent(a) = = MostFrequent(c)): s1 = a s2 = c freq = MostFrequent(a) else : s1 = b s2 = c freq = MostFrequent(b) # Pointer to iterate strings i, j = 0 , 0 # Traversal using the # two-pointer approach while (i < len (s1) and j < len (s2)): # if current character # is not most frequent while (i < len (s1) and s1[i] ! = freq): print (s1[i], end = "") i + = 1 # if current character # is not most frequent while (j < len (s2) and s2[j] ! = freq): print (s2[j], end = "") j + = 1 # If end of string is reached if (i = = len (s1) or j = = len (s2)): break # If both string character # are same as most frequent if (s1[i] = = s2[j]): print (s1[i], end = "") i + = 1 j + = 1 else : print (s1[i], end = "") i + = 1 # Print leftover characters # of the string s1 while (i < len (s1)): print (s1[i], end = "") i + = 1 # Print leftover characters # of the string s2 while (j < len (s2)): print (s2[j], end = "") j + = 1 # Driver Code if __name__ = = "__main__" : a = "00" b = "11" c = "01" findStr(a, b, c) # This code is contributed by rakeshsahni |
Javascript
<script> // JavaScript code for the above approach // Function to find most frequent // character in the given string function MostFrequent(s) { // Stores the frequency of // 0 and 1 respectively let arr = new Array(2).fill(0) for (let i = 0; i < s.length; i++) { let ch = s[i]; arr[ch.charCodeAt(0) - '0' .charCodeAt(0)]++; } // Stores most frequent character let result = arr[0] > arr[1] ? '0' : '1' ; // Return Answer return result; } // Function to find a Binary String of // at most 3N characters having at least // two of the given three strings of 2N // characters as one of its subsequence function findStr(a, b, c) { // Stores most frequent char let freq; // Stores the respective string // with most frequent values let s1, s2; // Code to find the set of // two strings with same // most frequent characters if (MostFrequent(a) == MostFrequent(b)) { s1 = a; s2 = b; freq = MostFrequent(a); } else if (MostFrequent(a) == MostFrequent(c)) { s1 = a; s2 = c; freq = MostFrequent(a); } else { s1 = b; s2 = c; freq = MostFrequent(b); } // Pointer to iterate strings let i = 0, j = 0; // Traversal using the // two-pointer approach while (i < s1.length && j < s2.length) { // if current character // is not most frequent while (i < s1.length && s1[i] != freq) { document.write(s1[i++]); } // if current character // is not most frequent while (j < s2.length && s2[j] != freq) { document.write(s2[j++]); } // If end of string is reached if (i == s1.length || j == s2.length) break ; // If both string character // are same as most frequent if (s1[i] == s2[j]) { document.write(s1[i]); i++; j++; } else { document.write(s1[i]); i++; } } // Print leftover characters // of the string s1 while (i < s1.length) { document.write(s1[i++]); } // Print leftover characters // of the string s2 while (j < s2.length) { document.write(s2[j++]); } } // Driver Code let a, b, c; a = "00" ; b = "11" ; c = "01" ; findStr(a, b, c); // This code is contributed by Potta Lokesh </script> |
011
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us