Remove Invalid Parenthesis

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

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






Video Solution

Code Solution

Run
 
Run
Id Name