Modify a numeric string to a balanced parentheses by replacements

Given a numeric string S made up of characters '1', '2' and '3' only, the task is to replace characters with either an open bracket ( '(' ) or a closed bracket ( ')' ) such that the newly formed string becomes a balanced bracket sequence.

Note: All occurrences of a character must be replaced by the same parentheses.

Examples:

Input: S = "1123"
Output: Yes, (())
Explanation: Replacing occurrences of character '1' with '(', '2' with ')' and '3' with ')'. Therefore, the obtained bracket sequence is “(())”, which is balanced.

Input: S = "1121"
Output: No

Approach: The given problem can be solved based on the following observations:

• For a balanced bracket sequence, it is necessary for the first and last characters to be open and closed brackets respectively. Therefore, the first and the last characters should be different.
• If the first and the last characters of a string are the same, then it is impossible to obtain a balanced bracket sequence.
• If the first and last characters of a string are different, then they are replaced by open and closed brackets respectively. The third character is replaced either by open or closed brackets.
• Check for both ways of replacements one by one for the remaining third character.
• If both replacements of the third remaining character can't make a balanced bracket sequence, then it is impossible to make a balanced bracket sequence.

Follow the steps below to solve the given problem:

• Check if the first and last characters of the string S are equal or not. If found to be true, then print "No" and return.
• Initialize two variables, say cntforOpen and cntforClose, to store the count of open and closed brackets.
• Iterate over the characters of the string and perform the following operations:
  • If the current character is the same as the first character of the string, increment cntforOpen.
  • If the current character is the same as the last character of the string, decrement cntforOpen.
  • For the remaining third character, increment cntforOpen, i.e. replacing that character with '('.
  • If at any instant, cntforOpen is found to be negative, then a balanced bracket sequence cannot be obtained.
• Similarly, check using cntforClose variable, i.e. replacing the third character with ')'.
• If none of the above two methods generates a balanced bracket sequence, then print "No". Otherwise, print "Yes".

Below is the implementation of the above approach:  

// C++ program for the above approach #include <iostream> using namespace std; // Function to check if the given // string can be converted to a // balanced bracket sequence or not void balBracketSequence(string str) {  int n = str.size();  // Check if the first and  // last characters are equal  if (str[0]  == str[n - 1])  {  cout << "No" << endl;  }  else {  // Initialize two variables to store  // the count of open and closed brackets  int cntForOpen = 0, cntForClose = 0;  int check = 1;  for (int i = 0; i < n; i++) {  // If the current character is  // same as the first character  if (str[i] == str[0])  cntForOpen++;  // If the current character is  // same as the last character  else if (str[i] == str[n - 1])  cntForOpen--;  else  cntForOpen++;  // If count of open brackets  // becomes less than 0  if (cntForOpen < 0) {  check = 0;  break;  }  }  if (check && cntForOpen == 0) {  cout << "Yes, ";  // Print the new string  for (int i = 0; i < n; i++) {  if (str[i] == str[n - 1])  cout << ')';  else  cout << '(';  }  return;  }  else {  for (int i = 0; i < n; i++) {  // If the current character is  // same as the first character  if (str[i] == str[0])  cntForClose++;  else  cntForClose--;  // If bracket sequence  // is not balanced  if (cntForClose  < 0) {  check = 0;  break;  }  }  // Check for unbalanced  // bracket sequence  if (check  && cntForClose  == 0) {  cout << "Yes, ";  // Print the sequence  for (int i = 0; i < n;  i++) {  if (str[i] == str[0])  cout << '(';  else  cout << ')';  }  return;  }  }  cout << "No";  } } // Driver Code int main() {  // Given Input  string str = "123122";  // Function Call  balBracketSequence(str);  return 0; } 

// Java program for the above approach import java.util.*; class GFG{ // Function to check if the given // string can be converted to a // balanced bracket sequence or not static void balBracketSequence(String str) {  int n = str.length();  // Check if the first and  // last characters are equal  if (str.charAt(0)  == str.charAt(n - 1))  {  System.out.println("No");  }  else {  // Initialize two variables to store  // the count of open and closed brackets  int cntForOpen = 0, cntForClose = 0;  int check = 1;  for (int i = 0; i < n; i++) {  // If the current character is  // same as the first character  if (str.charAt(i) == str.charAt(0))  cntForOpen++;  // If the current character is  // same as the last character  else if (str.charAt(i) == str.charAt(n - 1))  cntForOpen -= 1;  else  cntForOpen += 1;  // If count of open brackets  // becomes less than 0  if (cntForOpen < 0) {  check = 0;  break;  }  }  if (check != 0 && cntForOpen == 0) {  System.out.print("Yes, ");  // Print the new string  for (int i = 0; i < n; i++) {  if (str.charAt(i) == str.charAt(n - 1))  System.out.print(')');  else  System.out.print('(');  }  return;  }  else {  for (int i = 0; i < n; i++) {  // If the current character is  // same as the first character  if (str.charAt(i) == str.charAt(0))  cntForClose++;  else  cntForClose--;  // If bracket sequence  // is not balanced  if (cntForClose  < 0) {  check = 0;  break;  }  }  // Check for unbalanced  // bracket sequence  if (check != 0  && cntForClose  == 0) {  System.out.print("Yes, ");  // Print the sequence  for (int i = 0; i < n;  i++) {  if (str.charAt(i) == str.charAt(0))  System.out.print('(');  else  System.out.print(')');  }  return;  }  }  System.out.print("No");  } } // Driver Code public static void main(String args[]) {  // Given Input  String str = "123122";  // Function Call  balBracketSequence(str); } } // This code is contributed by ipg2016107. 

# Python program for the above approach; # Function to check if the given # string can be converted to a # balanced bracket sequence or not def balBracketSequence(str): n = len(str) # Check if the first and # last characters are equal if (str[0] == str[n - 1]): print("No", end="") else: # Initialize two variables to store # the count of open and closed brackets cntForOpen = 0 cntForClose = 0 check = 1 for i in range(n): # If the current character is # same as the first character if (str[i] == str[0]): cntForOpen += 1 # If the current character is # same as the last character elif str[i] == str[n - 1] : cntForOpen -= 1 else: cntForOpen += 1 # If count of open brackets # becomes less than 0 if (cntForOpen < 0): check = 0 break if (check and cntForOpen == 0): print("Yes, ", end="") # Print the new string for i in range(n): if (str[i] == str[n - 1]): print(')', end="") else: print('(', end="") return else: for i in range(n): # If the current character is # same as the first character if (str[i] == str[0]): cntForClose += 1 else: cntForClose -= 1 # If bracket sequence # is not balanced if (cntForClose < 0): check = 0 break # Check for unbalanced # bracket sequence if (check and cntForClose == 0): print("Yes, ", end="") # Print the sequence for i in range(n): if (str[i] == str[0]): print('(', end="") else: print(')', end="") return print("NO", end="") # Driver Code # Given Input str = "123122" # Function Call balBracketSequence(str) # This code is contributed by gfgking 

// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if the given // string can be converted to a // balanced bracket sequence or not static void balBracketSequence(string str) {  int n = str.Length;    // Check if the first and  // last characters are equal  if (str[0] == str[n - 1])  {  Console.Write("No");  }  else  {    // Initialize two variables to store  // the count of open and closed brackets  int cntForOpen = 0, cntForClose = 0;  int check = 1;    for(int i = 0; i < n; i++)   {    // If the current character is  // same as the first character  if (str[i] == str[0])  cntForOpen++;  // If the current character is  // same as the last character  else if (str[i] == str[n - 1])  cntForOpen--;  else  cntForOpen++;  // If count of open brackets  // becomes less than 0  if (cntForOpen < 0)  {  check = 0;  break;  }  }  if (check != 0 && cntForOpen == 0)   {  Console.Write("Yes, ");  // Print the new string  for(int i = 0; i < n; i++)  {  if (str[i] == str[n - 1])  Console.Write(')');  else  Console.Write('(');  }  return;  }  else   {  for(int i = 0; i < n; i++)   {    // If the current character is  // same as the first character  if (str[i] == str[0])  cntForClose++;  else  cntForClose--;  // If bracket sequence  // is not balanced  if (cntForClose < 0)   {  check = 0;  break;  }  }  // Check for unbalanced  // bracket sequence  if (check != 0 && cntForClose == 0)   {  Console.Write("Yes, ");  // Print the sequence  for(int i = 0; i < n; i++)  {  if (str[i] == str[0])  Console.Write('(');  else  Console.Write(')');  }  return;  }  }  Console.Write("No");  } } // Driver Code public static void Main() {    // Given Input  string str = "123122";  // Function Call  balBracketSequence(str); } } // This code is contributed by sanjoy_62 

 <script>  // JavaScript program for the above approach; // Function to check if the given // string can be converted to a // balanced bracket sequence or not function balBracketSequence(str) {  let n = str.length;  // Check if the first and  // last characters are equal  if (str[0]  == str[n - 1])  {  document.write( "No");  }  else {  // Initialize two variables to store  // the count of open and closed brackets  let cntForOpen = 0, cntForClose = 0;  let check = 1;  for (let i = 0; i < n; i++) {  // If the current character is  // same as the first character  if (str[i] == str[0])  cntForOpen++;  // If the current character is  // same as the last character  else if (str[i] == str[n - 1])  cntForOpen--;  else  cntForOpen++;  // If count of open brackets  // becomes less than 0  if (cntForOpen < 0) {  check = 0;  break;  }  }  if (check && cntForOpen == 0) {  document.write("Yes, ");  // Print the new string  for (let i = 0; i < n; i++) {  if (str[i] == str[n - 1])  document.write(')');  else  document.write('(');  }  return;  }  else {  for (let i = 0; i < n; i++) {  // If the current character is  // same as the first character  if (str[i] == str[0])  cntForClose++;  else  cntForClose--;  // If bracket sequence  // is not balanced  if (cntForClose  < 0) {  check = 0;  break;  }  }  // Check for unbalanced  // bracket sequence  if (check  && cntForClose  == 0) {  document.write("Yes, ");  // Print the sequence  for (let i = 0; i < n;  i++) {  if (str[i] == str[0])  document.write('(');  else  document.write(')');  }  return;  }  }  document.write("NO") ;  } } // Driver Code  // Given Input  let str = "123122";  // Function Call  balBracketSequence(str);    // This code is contributed by Potta Lokesh  </script> 

Yes, ()(())

Time Complexity: O(N)
Auxiliary Space: O(1)