Most frequent character in a string after replacing all occurrences of X in a Binary String
Given a string S of length N consisting of 1, 0, and X, the task is to print the character (β1β or β0β) with the maximum frequency after replacing every occurrence of X as per the following conditions:
- If the character present adjacently to the left of X is 1, replace X with 1.
- If the character present adjacently to the right of X is 0, replace X with 0.
- If both the above conditions are satisfied, X remains unchanged.
Note: If the frequency of 1 and 0 is the same after replacements, then print X.
Examples:
Input: S = βXX10XX10XXX1XXβ
Output: 1
Explanation:
Operation 1: S = βX11001100X1XXβ
Operation 2: S = β111001100X1XXβ
No further replacements are possible.
Hence, the frequencies of β1β and β0β are 6 and 4 respectively.Input: S = β0XXX1β
Output: X
Explanation:
Operation 1: S = β00X11β
No further replacements are possible.
Hence, the frequencies of both β1β and β0β are 2.
Approach: The given problem can be solved based on the following observations:
- All the βXβs lying between β1β and β0β (e.g. 1XXX0) is of no significance because neither of β1β and β0β can convert it.
- All the βXβs lying between β0β and β1β (e.g. 0XXX1) is also of no significance because it will contribute equally to both 1 and 0. Consider any substring of the form β0Xβ¦.X1β, then after changing the first occurrence of X from the start and the end of the string, the actual frequency of 0 and 1 in the substring remains unchanged.
From the above observations it can be concluded that the result depends upon the following conditions:
- The count of β1β and β0β in the original string.
- The frequency of X that are present between two consecutive 0s or two consecutive 1s, i.e. β0XXX0β and β1XXXX1β respectively.
- The number of continuous βXβ which are present at the starting of string and has a right end β1β, i.e. βXXXX1β¦..β.
- The number of continuous βXβs which are present at end of the string and has a left end β0β i.e., β¦..0XXX.
Hence, count the number of 1s and 0s as per the above conditions and print the resultant count.
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 the most frequent // character after replacing X with // either '0' or '1' according as per // the given conditions void maxOccurringCharacter(string s) { // Store the count of 0s and // 1s in the string S int count0 = 0, count1 = 0; // Count the frequency of // 0 and 1 for ( int i = 0; i < s.length(); i++) { // If the character is 1 if (s[i] == '1' ) { count1++; } // If the character is 0 else if (s[i] == '0' ) { count0++; } } // Stores first occurrence of 1 int prev = -1; for ( int i = 0; i < s.length(); i++) { if (s[i] == '1' ) { prev = i; break ; } } // Traverse the string to count // the number of X between two // consecutive 1s for ( int i = prev + 1; i < s.length(); i++) { // If the current character // is not X if (s[i] != 'X' ) { // If the current character // is 1, add the number of // Xs to count1 and set // prev to i if (s[i] == '1' ) { count1 += i - prev - 1; prev = i; } // Otherwise else { // Find next occurrence // of 1 in the string bool flag = true ; for ( int j = i + 1; j < s.length(); j++) { if (s[j] == '1' ) { flag = false ; prev = j; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break // out of the loop else { i = s.length(); } } } } // Store the first occurrence of 0 prev = -1; for ( int i = 0; i < s.length(); i++) { if (s[i] == '0' ) { prev = i; break ; } } // Repeat the same procedure to // count the number of X between // two consecutive 0s for ( int i = prev + 1; i < s.length(); i++) { // If the current character is not X if (s[i] != 'X' ) { // If the current character is 0 if (s[i] == '0' ) { // Add the count of Xs to count0 count0 += i - prev - 1; // Set prev to i prev = i; } // Otherwise else { // Find the next occurrence // of 0 in the string bool flag = true ; for ( int j = i + 1; j < s.length(); j++) { if (s[j] == '0' ) { prev = j; flag = false ; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break out // of the loop else { i = s.length(); } } } } // Count number of X present in // the starting of the string // as XXXX1... if (s[0] == 'X' ) { // Store the count of X int count = 0; int i = 0; while (s[i] == 'X' ) { count++; i++; } // Increment count1 by // count if the condition // is satisfied if (s[i] == '1' ) { count1 += count; } } // Count the number of X // present in the ending of // the string as ...XXXX0 if (s[(s.length() - 1)] == 'X' ) { // Store the count of X int count = 0; int i = s.length() - 1; while (s[i] == 'X' ) { count++; i--; } // Increment count0 by // count if the condition // is satisfied if (s[i] == '0' ) { count0 += count; } } // If count of 1 is equal to // count of 0, print X if (count0 == count1) { cout << "X" << endl; } // Otherwise, if count of 1 // is greater than count of 0 else if (count0 > count1) { cout << 0 << endl; } // Otherwise, print 0 else cout << 1 << endl; } // Driver Code int main() { string S = "XX10XX10XXX1XX" ; maxOccurringCharacter(S); } // This code is contributed by SURENDAR_GANGWAR. |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the most frequent // character after replacing X with // either '0' or '1' according as per // the given conditions public static void maxOccurringCharacter(String s) { // Store the count of 0s and // 1s in the string S int count0 = 0 , count1 = 0 ; // Count the frequency of // 0 and 1 for ( int i = 0 ; i < s.length(); i++) { // If the character is 1 if (s.charAt(i) == '1' ) { count1++; } // If the character is 0 else if (s.charAt(i) == '0' ) { count0++; } } // Stores first occurrence of 1 int prev = - 1 ; for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == '1' ) { prev = i; break ; } } // Traverse the string to count // the number of X between two // consecutive 1s for ( int i = prev + 1 ; i < s.length(); i++) { // If the current character // is not X if (s.charAt(i) != 'X' ) { // If the current character // is 1, add the number of // Xs to count1 and set // prev to i if (s.charAt(i) == '1' ) { count1 += i - prev - 1 ; prev = i; } // Otherwise else { // Find next occurrence // of 1 in the string boolean flag = true ; for ( int j = i + 1 ; j < s.length(); j++) { if (s.charAt(j) == '1' ) { flag = false ; prev = j; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break // out of the loop else { i = s.length(); } } } } // Store the first occurrence of 0 prev = - 1 ; for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == '0' ) { prev = i; break ; } } // Repeat the same procedure to // count the number of X between // two consecutive 0s for ( int i = prev + 1 ; i < s.length(); i++) { // If the current character is not X if (s.charAt(i) != 'X' ) { // If the current character is 0 if (s.charAt(i) == '0' ) { // Add the count of Xs to count0 count0 += i - prev - 1 ; // Set prev to i prev = i; } // Otherwise else { // Find the next occurrence // of 0 in the string boolean flag = true ; for ( int j = i + 1 ; j < s.length(); j++) { if (s.charAt(j) == '0' ) { prev = j; flag = false ; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break out // of the loop else { i = s.length(); } } } } // Count number of X present in // the starting of the string // as XXXX1... if (s.charAt( 0 ) == 'X' ) { // Store the count of X int count = 0 ; int i = 0 ; while (s.charAt(i) == 'X' ) { count++; i++; } // Increment count1 by // count if the condition // is satisfied if (s.charAt(i) == '1' ) { count1 += count; } } // Count the number of X // present in the ending of // the string as ...XXXX0 if (s.charAt(s.length() - 1 ) == 'X' ) { // Store the count of X int count = 0 ; int i = s.length() - 1 ; while (s.charAt(i) == 'X' ) { count++; i--; } // Increment count0 by // count if the condition // is satisfied if (s.charAt(i) == '0' ) { count0 += count; } } // If count of 1 is equal to // count of 0, print X if (count0 == count1) { System.out.println( "X" ); } // Otherwise, if count of 1 // is greater than count of 0 else if (count0 > count1) { System.out.println( 0 ); } // Otherwise, print 0 else System.out.println( 1 ); } // Driver Code public static void main(String[] args) { String S = "XX10XX10XXX1XX" ; maxOccurringCharacter(S); } } |
Python3
# Python program for the above approach # Function to find the most frequent # character after replacing X with # either '0' or '1' according as per # the given conditions def maxOccurringCharacter(s): # Store the count of 0s and # 1s in the S count0 = 0 count1 = 0 # Count the frequency of # 0 and 1 for i in range ( len (s)): # If the character is 1 if (s[i] = = '1' ) : count1 + = 1 # If the character is 0 elif (s[i] = = '0' ) : count0 + = 1 # Stores first occurrence of 1 prev = - 1 for i in range ( len (s)): if (s[i] = = '1' ) : prev = i break # Traverse the to count # the number of X between two # consecutive 1s for i in range (prev + 1 , len (s)): # If the current character # is not X if (s[i] ! = 'X' ) : # If the current character # is 1, add the number of # Xs to count1 and set # prev to i if (s[i] = = '1' ) : count1 + = i - prev - 1 prev = i # Otherwise else : # Find next occurrence # of 1 in the string flag = True for j in range (i + 1 , len (s)): if (s[j] = = '1' ) : flag = False prev = j break # If it is found, # set i to prev if (flag = = False ) : i = prev # Otherwise, break # out of the loop else : i = len (s) # Store the first occurrence of 0 prev = - 1 for i in range ( 0 , len (s)): if (s[i] = = '0' ) : prev = i break # Repeat the same procedure to # count the number of X between # two consecutive 0s for i in range (prev + 1 , len (s)): # If the current character is not X if (s[i] ! = 'X' ) : # If the current character is 0 if (s[i] = = '0' ) : # Add the count of Xs to count0 count0 + = i - prev - 1 # Set prev to i prev = i # Otherwise else : # Find the next occurrence # of 0 in the string flag = True for j in range (i + 1 , len (s)): if (s[j] = = '0' ) : prev = j flag = False break # If it is found, # set i to prev if (flag = = False ) : i = prev # Otherwise, break out # of the loop else : i = len (s) # Count number of X present in # the starting of the string # as XXXX1... if (s[ 0 ] = = 'X' ) : # Store the count of X count = 0 i = 0 while (s[i] = = 'X' ) : count + = 1 i + = 1 # Increment count1 by # count if the condition # is satisfied if (s[i] = = '1' ) : count1 + = count # Count the number of X # present in the ending of # the as ...XXXX0 if (s[( len (s) - 1 )] = = 'X' ) : # Store the count of X count = 0 i = len (s) - 1 while (s[i] = = 'X' ) : count + = 1 i - = 1 # Increment count0 by # count if the condition # is satisfied if (s[i] = = '0' ) : count0 + = count # If count of 1 is equal to # count of 0, print X if (count0 = = count1) : print ( "X" ) # Otherwise, if count of 1 # is greater than count of 0 elif (count0 > count1) : print ( 0 ) # Otherwise, print 0 else : print ( 1 ) # Driver Code S = "XX10XX10XXX1XX" maxOccurringCharacter(S) # This code is contributed by sanjoy_62. |
C#
// C# program for the above approach using System; public class GFG { // Function to find the most frequent // character after replacing X with // either '0' or '1' according as per // the given conditions public static void maxOccurringCharacter( string s) { // Store the count of 0s and // 1s in the string S int count0 = 0, count1 = 0; // Count the frequency of // 0 and 1 for ( int i = 0; i < s.Length; i++) { // If the character is 1 if (s[i] == '1' ) { count1++; } // If the character is 0 else if (s[i] == '0' ) { count0++; } } // Stores first occurrence of 1 int prev = -1; for ( int i = 0; i < s.Length; i++) { if (s[i] == '1' ) { prev = i; break ; } } // Traverse the string to count // the number of X between two // consecutive 1s for ( int i = prev + 1; i < s.Length; i++) { // If the current character // is not X if (s[i] != 'X' ) { // If the current character // is 1, add the number of // Xs to count1 and set // prev to i if (s[i] == '1' ) { count1 += i - prev - 1; prev = i; } // Otherwise else { // Find next occurrence // of 1 in the string bool flag = true ; for ( int j = i + 1; j < s.Length; j++) { if (s[j] == '1' ) { flag = false ; prev = j; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break // out of the loop else { i = s.Length; } } } } // Store the first occurrence of 0 prev = -1; for ( int i = 0; i < s.Length; i++) { if (s[i] == '0' ) { prev = i; break ; } } // Repeat the same procedure to // count the number of X between // two consecutive 0s for ( int i = prev + 1; i < s.Length; i++) { // If the current character is not X if (s[i] != 'X' ) { // If the current character is 0 if (s[i] == '0' ) { // Add the count of Xs to count0 count0 += i - prev - 1; // Set prev to i prev = i; } // Otherwise else { // Find the next occurrence // of 0 in the string bool flag = true ; for ( int j = i + 1; j < s.Length; j++) { if (s[j] == '0' ) { prev = j; flag = false ; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break out // of the loop else { i = s.Length; } } } } // Count number of X present in // the starting of the string // as XXXX1... if (s[0] == 'X' ) { // Store the count of X int count = 0; int i = 0; while (s[i] == 'X' ) { count++; i++; } // Increment count1 by // count if the condition // is satisfied if (s[i] == '1' ) { count1 += count; } } // Count the number of X // present in the ending of // the string as ...XXXX0 if (s[s.Length - 1] == 'X' ) { // Store the count of X int count = 0; int i = s.Length - 1; while (s[i] == 'X' ) { count++; i--; } // Increment count0 by // count if the condition // is satisfied if (s[i] == '0' ) { count0 += count; } } // If count of 1 is equal to // count of 0, print X if (count0 == count1) { Console.WriteLine( "X" ); } // Otherwise, if count of 1 // is greater than count of 0 else if (count0 > count1) { Console.WriteLine(0); } // Otherwise, print 0 else Console.WriteLine(1); } // Driver Code public static void Main( string [] args) { string S = "XX10XX10XXX1XX" ; maxOccurringCharacter(S); } } // This code is contributed by AnkThon |
Javascript
<script> // javascript program for the above approach // Function to find the most frequent // character after replacing X with // either '0' or '1' according as per // the given conditions function maxOccurringCharacter(s) { // Store the count of 0s and // 1s in the string S var count0 = 0, count1 = 0; // Count the frequency of // 0 and 1 for ( var i = 0; i < s.length; i++) { // If the character is 1 if (s.charAt(i) == '1' ) { count1++; } // If the character is 0 else if (s.charAt(i) == '0' ) { count0++; } } // Stores first occurrence of 1 var prev = -1; for ( var i = 0; i < s.length; i++) { if (s.charAt(i) == '1' ) { prev = i; break ; } } // Traverse the string to count // the number of X between two // consecutive 1s for ( var i = prev + 1; i < s.length; i++) { // If the current character // is not X if (s.charAt(i) != 'X' ) { // If the current character // is 1, add the number of // Xs to count1 and set // prev to i if (s.charAt(i) == '1' ) { count1 += i - prev - 1; prev = i; } // Otherwise else { // Find next occurrence // of 1 in the string flag = true ; for ( var j = i + 1; j < s.length; j++) { if (s.charAt(j) == '1' ) { flag = false ; prev = j; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break // out of the loop else { i = s.length; } } } } // Store the first occurrence of 0 prev = -1; for ( var i = 0; i < s.length; i++) { if (s.charAt(i) == '0' ) { prev = i; break ; } } // Repeat the same procedure to // count the number of X between // two consecutive 0s for ( var i = prev + 1; i < s.length; i++) { // If the current character is not X if (s.charAt(i) != 'X' ) { // If the current character is 0 if (s.charAt(i) == '0' ) { // Add the count of Xs to count0 count0 += i - prev - 1; // Set prev to i prev = i; } // Otherwise else { // Find the next occurrence // of 0 in the string flag = true ; for ( var j = i + 1; j < s.length; j++) { if (s.charAt(j) == '0' ) { prev = j; flag = false ; break ; } } // If it is found, // set i to prev if (!flag) { i = prev; } // Otherwise, break out // of the loop else { i = s.length; } } } } // Count number of X present in // the starting of the string // as XXXX1... if (s.charAt(0) == 'X' ) { // Store the count of X var count = 0; var i = 0; while (s.charAt(i) == 'X' ) { count++; i++; } // Increment count1 by // count if the condition // is satisfied if (s.charAt(i) == '1' ) { count1 += count; } } // Count the number of X // present in the ending of // the string as ...XXXX0 if (s.charAt(s.length - 1) == 'X' ) { // Store the count of X var count = 0; var i = s.length - 1; while (s.charAt(i) == 'X' ) { count++; i--; } // Increment count0 by // count if the condition // is satisfied if (s.charAt(i) == '0' ) { count0 += count; } } // If count of 1 is equal to // count of 0, print X if (count0 == count1) { document.write( "X" ); } // Otherwise, if count of 1 // is greater than count of 0 else if (count0 > count1) { document.write(0); } // Otherwise, print 0 else document.write(1); } // Driver Code var S = "XX10XX10XXX1XX" ; maxOccurringCharacter(S); // This code is contributed by 29AjayKumar </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us