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.

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.

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 -

Create a stack.

Loop over the string.

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

If the character is ')':

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

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

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

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.