Given a string S of N characters consisting of ‘?’, ‘0‘, and ‘1‘ and two integers a and b, the task is to find a palindromic binary string with exactly a 0s and b 1s by replacing the ‘?‘ with either ‘0‘ or ‘1‘.
Examples:
Input: S = “10?????1”, a = 4, b = 4
Output: 10100101
Explanation: The output string is a palindromic binary string with exactly 4 0’s and 4 1’s.Input: S = “??????”, a = 5, b = 1
Output: -1
Explanation: There does not exist any palindromic string with exactly a 0’s and b 1’s.
Approach: The given problem can be solved by using the following observations:
- For the string S of N characters to be a palindrome, S[i] = S[N-i-1] must hold true for all values of i in the range [0, N).
- If only one of the S[i] and S[N-i-1] is equal to ‘?‘, then it must be replaced with the corresponding character of the other index.
- If the value of both S[i] and S[N-i-1] is ‘?‘, the most optimal choice is to replace both of them with the character whose required count is more.
Using the above-stated observations, follow the below steps to solve the problem:
- Traverse through the string in the range [0, N/2), and for the cases where only one of the S[i] and S[N – i – 1] is equal to ‘?‘, replace it with the corresponding character.
- Update the values of a and b by subtracting the count of ‘0‘ and ‘1‘ after the above operation. The count can be easily calculated using the std::count function.
- Now traverse the given string in the range [0, N/2), and if both S[i] = ‘?‘ and S[N-i-1] = ‘?‘, update their value with the character whose required count is more( i.e, with ‘0‘ if a>b otherwise with ‘1‘).
- In the case of odd string length with the middle character as ‘?‘, update it with character with the remaining count.
- If the value of a = 0 and b = 0, the string stored in S is the required string. Otherwise, the required string does not exist, hence return -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to convert the given string// to a palindrome with a 0's and b 1'sstring convertString(string S, int a, int b){ // Stores the size of the string int N = S.size(); // Loop to iterate over the string for (int i = 0; i < N / 2; ++i) { // If one of S[i] or S[N-i-1] is // equal to '?', replace it with // corresponding character if (S[i] == '?' && S[N - i - 1] != '?') { S[i] = S[N - i - 1]; } else if (S[i] != '?' && S[N - i - 1] == '?') { S[N - i - 1] = S[i]; } } // Subtract the count of 0 from the // required number of zeroes a = a - count(S.begin(), S.end(), '0'); // Subtract the count of 1 from // required number of ones b = b - count(S.begin(), S.end(), '1'); // Traverse the string for (int i = 0; i < N / 2; ++i) { // If both S[i] and S[N-i-1] are '?' if (S[i] == '?' && S[N - i - 1] == '?') { // If a is greater than b if (a > b) { // Update S[i] and S[N-i-1] to '0' S[i] = S[N - i - 1] = '0'; // Update the value of a a -= 2; } else { // Update S[i] and S[N-i-1] to '1' S[i] = S[N - i - 1] = '1'; // Update the value of b b -= 2; } } } // Case with middle character '?' // in case of odd length string if (S[N / 2] == '?') { // If a is greater than b if (a > b) { // Update middle character // with '0' S[N / 2] = '0'; a--; } else { // Update middle character // by '1' S[N / 2] = '1'; b--; } } // Return Answer if (a == 0 && b == 0) { return S; } else { return "-1"; }}// Driver Codeint main(){ string S = "10?????1"; int a = 4, b = 4; cout << convertString(S, a, b); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to convert the given string // to a palindrome with a 0's and b 1's static String convertString(String S, int a, int b) { // Stores the size of the string int N = S.length(); char[] str = S.toCharArray(); // Loop to iterate over the string for (int i = 0; i < N / 2; ++i) { // If one of S[i] or S[N-i-1] is // equal to '?', replace it with // corresponding character if (str[i] == '?' && str[N - i - 1] != '?') { str[i] = str[N - i - 1]; } else if (str[i] != '?' && str[N - i - 1] == '?') { str[N - i - 1] = str[i]; } } // Subtract the count of 0 from the // required number of zeroes int countA = 0, countB = 0; for (int i = 0; i < str.length; i++) { if (str[i] == '0') countA++; else if (str[i] == '1') countB++; } a = a - countA; // Subtract the count of 1 from // required number of ones b = b - countB; // Traverse the string for (int i = 0; i < N / 2; ++i) { // If both S[i] and S[N-i-1] are '?' if (str[i] == '?' && str[N - i - 1] == '?') { // If a is greater than b if (a > b) { // Update S[i] and S[N-i-1] to '0' str[i] = '0'; str[N - i - 1] = '0'; // Update the value of a a -= 2; } else { // Update S[i] and S[N-i-1] to '1' str[i] = '1'; str[N - i - 1] = '1'; // Update the value of b b -= 2; } } } // Case with middle character '?' // in case of odd length string if (str[N / 2] == '?') { // If a is greater than b if (a > b) { // Update middle character // with '0' str[N / 2] = '0'; a--; } else { // Update middle character // by '1' str[N / 2] = '1'; b--; } } // Return Answer if (a == 0 && b == 0) { return new String(str); } else { return "-1"; } } public static void main(String[] args) { String S = "10?????1"; int a = 4, b = 4; System.out.println(convertString(S, a, b)); }}// this code is contributed by phasing17 |
Python3
# Python program for the above approach# Function to convert the given string# to a palindrome with a 0's and b 1'sdef convertString(S, a, b): print(S) # Stores the size of the string N = len(S) # Loop to iterate over the string for i in range(0, N // 2): # If one of S[i] or S[N-i-1] is # equal to '?', replace it with # corresponding character if (S[i] == '?' and S[N - i - 1] != '?'): S[i] = S[N - i - 1] elif (S[i] != '?' and S[N - i - 1] == '?'): S[N - i - 1] = S[i] # Subtract the count of 0 from the # required number of zeroes cnt_0 = 0 for i in range(0, N): if (S[i] == '0'): cnt_0 += 1 a = a - cnt_0 # Subtract the count of 1 from # required number of ones cnt_1 = 0 for i in range(0, N): if (S[i] == '0'): cnt_1 += 1 b = b - cnt_1 # Traverse the string for i in range(0, N // 2): # If both S[i] and S[N-i-1] are '?' if (S[i] == '?' and S[N - i - 1] == '?'): # If a is greater than b if (a > b): # Update S[i] and S[N-i-1] to '0' S[i] = S[N - i - 1] = '0' # Update the value of a a -= 2 else: # Update S[i] and S[N-i-1] to '1' S[i] = S[N - i - 1] = '1' # Update the value of b b -= 2 # Case with middle character '?' # in case of odd length string if (S[N // 2] == '?'): # If a is greater than b if (a > b): # Update middle character # with '0' S[N // 2] = '0' a -= 1 else: # Update middle character # by '1' S[N // 2] = '1' b -= 1 # Return Answer if (a == 0 and b == 0): return S else: return "-1"# Driver CodeS = "10?????1"S = list(S)a = 4b = 4print("".join(convertString(S, a, b)))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG { // Function to convert the given string // to a palindrome with a 0's and b 1's static string convertString(string S, int a, int b) { // Stores the size of the string int N = S.Length; char[] str = S.ToCharArray(); // Loop to iterate over the string for (int i = 0; i < N / 2; ++i) { // If one of S[i] or S[N-i-1] is // equal to '?', replace it with // corresponding character if (str[i] == '?' && str[N - i - 1] != '?') { str[i] = str[N - i - 1]; } else if (str[i] != '?' && str[N - i - 1] == '?') { str[N - i - 1] = str[i]; } } // Subtract the count of 0 from the // required number of zeroes int countA = 0, countB = 0; for (int i = 0; i < str.Length; i++) { if (str[i] == '0') countA++; else if (str[i] == '1') countB++; } a = a - countA; // Subtract the count of 1 from // required number of ones b = b - countB; // Traverse the string for (int i = 0; i < N / 2; ++i) { // If both S[i] and S[N-i-1] are '?' if (str[i] == '?' && str[N - i - 1] == '?') { // If a is greater than b if (a > b) { // Update S[i] and S[N-i-1] to '0' str[i] = '0'; str[N - i - 1] = '0'; // Update the value of a a -= 2; } else { // Update S[i] and S[N-i-1] to '1' str[i] = '1'; str[N - i - 1] = '1'; // Update the value of b b -= 2; } } } // Case with middle character '?' // in case of odd length string if (str[N / 2] == '?') { // If a is greater than b if (a > b) { // Update middle character // with '0' str[N / 2] = '0'; a--; } else { // Update middle character // by '1' str[N / 2] = '1'; b--; } } // Return Answer if (a == 0 && b == 0) { return new String(str); } else { return "-1"; } } // Driver Code public static void Main() { string S = "10?????1"; int a = 4, b = 4; Console.Write(convertString(S, a, b)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach // Function to convert the given string // to a palindrome with a 0's and b 1's const convertString = (S, a, b) => { // Stores the size of the string let N = S.length; // Loop to iterate over the string for (let i = 0; i < parseInt(N / 2); ++i) { // If one of S[i] or S[N-i-1] is // equal to '?', replace it with // corresponding character if (S[i] == '?' && S[N - i - 1] != '?') { S[i] = S[N - i - 1]; } else if (S[i] != '?' && S[N - i - 1] == '?') { S[N - i - 1] = S[i]; } } // Subtract the count of 0 from the // required number of zeroes let cnt_0 = 0; for (let i = 0; i < N; ++i) { if (S[i] == '0') cnt_0++; } a = a - cnt_0; // Subtract the count of 1 from // required number of ones let cnt_1 = 0; for (let i = 0; i < N; ++i) { if (S[i] == '0') cnt_1++; } b = b - cnt_1; // Traverse the string for (let i = 0; i < parseInt(N / 2); ++i) { // If both S[i] and S[N-i-1] are '?' if (S[i] == '?' && S[N - i - 1] == '?') { // If a is greater than b if (a > b) { // Update S[i] and S[N-i-1] to '0' S[i] = S[N - i - 1] = '0'; // Update the value of a a -= 2; } else { // Update S[i] and S[N-i-1] to '1' S[i] = S[N - i - 1] = '1'; // Update the value of b b -= 2; } } } // Case with middle character '?' // in case of odd length string if (S[parseInt(N / 2)] == '?') { // If a is greater than b if (a > b) { // Update middle character // with '0' S[parseInt(N / 2)] = '0'; a--; } else { // Update middle character // by '1' S[parseInt(N / 2)] = '1'; b--; } } // Return Answer if (a == 0 && b == 0) { return S; } else { return "-1"; } } // Driver Code let S = "10?????1"; S = S.split(''); let a = 4, b = 4; document.write(convertString(S, a, b).join(''));// This code is contributed by rakeshsahni</script> |
Output:
10100101
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
