# Make Palindrome binary string with exactly a 0s and b 1s by replacing wild card ?

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:S = “10?????1”, a = 4, b = 4Output:10100101Explanation:The output string is a palindromic binary string with exactly 4 0’s and 4 1’s.

Input:S = “??????”, a = 5, b = 1Output:-1Explanation: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's` `string 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 Code` `int` `main()` `{` ` ` `string S = ` `"10?????1"` `;` ` ` `int` `a = 4, b = 4;` ` ` `cout << convertString(S, a, b);` ` ` `return` `0;` `}` |

## Python3

`# Python program for the above approach` `# Function to convert the given string` `# to a palindrome with a 0's and b 1's` `def` `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 Code` `S ` `=` `"10?????1"` `S ` `=` `list` `(S)` `a ` `=` `4` `b ` `=` `4` `print` `("".join(convertString(S, a, b)))` `# This code is contributed by gfgking` |

## 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)