Remove Invalid Parenthesis

1. You are given a string, which represents an expression having only opening and closing parenthesis.
2. You have to remove minimum number of parenthesis to make the given expression valid.
3. If there are multiple answers, you have to print all of them.

Note -> Check out the question video and write the recursive code as it is intended without changing signature. The judge can't 
               force you but intends you to teach a concept.

Input Format

A string containing only opening and closing parenthesis

Output Format

Print all the Valid expressions.
Check the sample ouput and question video.

Question Video Constraints

1 <= length of string <= 20

Sample Input

()())()

Sample Output

(())()
()()()

• Editorial

  The DFS approach will be discussed here.

  First find the minimum numbers of brackets that needs to be removed to make the string balanced. Let that number be minRemoval. We will then use recursion and at every level remove each character of the string one by one and make a call to the next level. At level we will place string and the options will be each character of the string. We will pass the rest of the string (Current string minus the current character) to the next level. We will also reduce the minRemoval by 1 at each level.

  When the minRemoval be zero, we will check whether the current string is balanced. If it is balanced, we will print it.

  To avoid duplicate answers, we use HashSet. If the string after minRemoval removals is balanced and not present in the set, we will print it and add it to the set.

  Algorithm to calculate minRemoval -

  1 - Create a stack.

  2 - Loop over the string.

  3 - If the character is '(' , push it to the stack

  4 - If the character is ')' -

        4.1 - If the stack is empty, push it to the stack.

        4.2 - If the top of the stack is '(', use pop operation.

        4.3 - If the top of the stack is ')', push it to the stack.

  5 - The size of the stack at the end of the loop will give us the answer.

  Why it is working?

  We know '(' and ')' forms a pair. Whenever '(', we have no choice but to push it to the stack. Whenever, ')', we check whether the size of stack is greater than zero and if it greater than zero, whether the top of stack contains '('. If the top of stack contains '(', we pop it as a pair is completed.

  Code to calculate minRemoval -

  public static int getMin(String str) {
                                          Stack < Character > st = new Stack < > ();
                                          for (int i = 0; i < str.length(); i++) {
                                              char ch = str.charAt(i);
                                              if (ch == '(') {
                                                  st.push(ch);
                                              } else {
                                                  if (st.size() == 0 || st.peek() == ')') {
                                                      st.push(ch);
                                                  } else if (st.peek() == '(') {
                                                      st.pop();
                                                  }
                                              }
                                          }
                                          return st.size();
                                  }

  java false

  Signature for Recursion function -

  public static void solution(String str, int minRemoval, HashSet ans)

  str - Input string

  minRemoval - Minimum numbers of brackets to be removed to make the string balanced

  ans - HashSet to avoid duplicates

  Code - 

  public static void solution(String str, int minRemoval, HashSet
   ans) {
                                  
                                          if (minRemoval == 0) {
                                              int mrnow = getMin(str);
                                              if (mrnow == 0) {
                                                  if (!ans.contains(str)) {
                                                      System.out.println(str);
                                                      ans.add(str);
                                                  }
                                                  return;
                                              }
                                          }
                                  
                                          for (int i = 0; i < str.length(); i++) {
                                              String left = str.substring(0, i);
                                              String right = str.substring(i + 1);
                                              solution(left + right, minRemoval - 1, ans);
                                          }
                                      }

  java false

  Code Explained -

  As discussed earlier, at levels we keep the current string and minRemoval. The options will be to remove every character one by one and call the recursive function where the string at next level will be equal to the current string minus the current character. At every recursion call we will decrease the minRemoval.

  When minRemoval will be zero, it means we have removed the minRemoval number of characters, we will hit the base case.

  Base Case -

  We will check whether the string is balanced now or not by calculating the minimum number of brackets needed from the current string to make it balanced. If the answer is zero, it means it is balanced. We will use HashMap to avoid duplicates.

• Asked in Companies
• Related Topics