Redirecting to
NADOS


  Prev   Next

Remove Invalid Parentheses







When everything seems to be going against you, remember that the airplane takes off against the wind, not with it.
~Henry Ford

Remove Invalid Parentheses

Welcome Back Reader!

We hope that you are doing great with Recursion so far. In this article we will discuss about the next problem based on "Recursion and Backtracking"i.e. "Remove Invalid Parentheses".

Before you move any further, it is advised that you give this problem a fair try. Let's jump to the problem.

Importan Link : Problem Link, Solution Video Link

Understanding the problem:

In this problem you are given a string, which represents an expression having only opening and closing parenthesis.

All you have to do is to remove the minimum number of parentheses to make the given expression valid.

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.

For example:

Sample Input: ()())()
Sample Output: (())()
()()()

How?

Simply by removing the 2nd and 4th bracket, one at time from the sample input, we get the desired output.

For more clarity of the question, watch part of the video.

Approach:

  • The DFS approach will be discussed here.
  • First find the minimum numbers of brackets that need 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 a 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 is 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 ')':
    1. If the stack is empty, push it to the stack.
    2. If the top of the stack is '(', use pop operation.
    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 is it 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 the stack is greater than zero and if it is greater than zero, whether the top of stack contains '('. If the top of the stack contains '(', we pop it as a pair is completed.

For more clarity of this part, watch part of the video.

Let's try to code this!

Code to calculate minRemoval:

public static int getMin(String str) { Stack 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;
                                            true";
                                        

                                
                                            

                                                

                                                    For more clarity of this code, watch part of the video. 3 
                                                

                                                

                                                    
                                                

                                            

                                
                                            
Solution:

                                            

                                                
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.
                                                    
    • 
                                                

                                				

                                                

                                                    

                                                        public static void solution(String str, int minRemoval, HashSet ans) {
                                                            if (IsValid(str) == true) {
                                                            if(!ans.contains(str)) {
                                                            System.out.println(str);
                                                            ans.add(str);
                                                            }
                                                            return;
                                                            }
                                
                                                            if (minRemoval == 0) {
                                                            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;
                                                    true";
                                                    

                                					
                                                    

                                                        
    
                                                            
  • 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.
                                                            
    • 
                                                        

                                                        

                                                            For more clarity of this part, watch part of the video. 
                                                        

                                                        

                                                            
                                                        

                                                    

                                                    

                                                        
Complexities: 

                                                        
Time Complexity:

                                                        

                                                            

                                                                

                                                                    O()
                                                                

                                                            

                                                            
Space Complexity:

                                                            

                                                                

                                                                    O()
                                                                

                                                            

                                                        

                                                    

                                                    

                                                        

                                                            Complete Code:
                                                        

                                                    

                                
                                                    

                                                        
 
                                                            import java.io.*;
                                                            import java.util.*;
                                                            public class Main {
                                
                                                            public static void main(String[] args) {
                                                            Scanner scn = new Scanner(System.in);
                                                            String str = scn.next();
                                                            solution(str, getMin(str),new HashSet<>());
                                                                }
                                
                                                                public static void solution(String str, int minRemoval, HashSet ans) {
                                                                    if (IsValid(str) == true) {
                                                                    if(!ans.contains(str)) {
                                                                    System.out.println(str);
                                                                    ans.add(str);
                                                                    }
                                                                    return;
                                                                    }
                                
                                                                    if (minRemoval == 0) {
                                                                    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); } }
                                                                        public static int getMin(String str) { Stack 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(); } private static boolean IsValid(String str) { int count=0;
                                                                                for(int i=0 ; i < str.length(); i++) { char ch=str.charAt(i); if(ch=='('
                                                                                ) { count++; }else if(ch==')' ) { count--; if(count < 0) { return false;
                                                                                } } } return count==0; } } 
                                                        

                                
                                                        
                                            

                                                        java;
                                                        true";
                                                    

                                
                                
                                                    

                                                        

                                                            We hope that this article was helpful. If somehow you are finding it difficult to understand
                                                            this problem then we advise you to watch our  video
                                                                lecture of this problem.
                                                        

                                                        
Trust me it will just get easier to understand after you have watched the solution video.

                                                        
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

                                                        
It is also advised that you follow the sequence of modules and questions which is there on  our website. 

                                                        
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
                                                        

                                                        
All the best for an exciting future!

                                                        
Happy Coding!

                                                    

                                                    

                                                        
Recursion

                                                        
Backtracking

                                                        
 Remove Invalid Parentheses

                                                    

                                                    

                                                        
Author:
                                                             Nikita Aggarwal
                                                        

                                                    

                                                

                                            

                                            

                                            

                                                

                                                

                                            

                                        

                                    

                                    
                                    
                                    
                                    
                                    
                                

                                            
                                
                        

            

        

    


   

   

       

           

               

                   
               

               

                   
 
               

   
   
               

   
                   

                       

                         
                       

                       

                         
                        
                         
                         
                         
                       

                       

                         

                           
                           Run
                         

                       

                       
                       
                                       

               

               

                   
                       
                   
               

   
           

           

               

   
   
               

                   

                       
                       
                   

               

   
               

   
                   

                       
                           

                               Id
                               Name