Remove Invalid Parentheses Explained using Stacks | Leetcode 301 (Valid Parentheses) Code in JAVA

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we explain the Remove Invalid Parenthesis problem using stacks and backtracking Java. In this problem:

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.

.....................................................................................................................................................................

Pepcoding has taken the initiative to provide counselling and learning resources to all curious, skilful and dedicated Indian coders. This video is part of the series to impart industry-level web development and programming skills in the community.

We also provide professional courses with live classes and placement opportunities.
DSA Level 1 and Level 2

Webinar on GATE Preparation

We are also available on the following social media platforms: -

HAPPY PROGRAMMING!
Pep it up.....

#recursion #backtracking #remove invalid parentheses

[vivek.tiwary]

This is most clear explanation in YouTube

[leetcode]

The way it is explained, its amazing, one can understand how to approach solution. Thanks for the video.

[prashanttrivedi]

Sir it amazing I like your teaching style thanks sir I have watched all level1 vedio and now I am here..

[priyanjanchaurasia]

TLE can be resolved if we pass another HashSet object in the recursive function to track if the string has been visited before. If the string is visited, simply return. otherwise, put the string in HashSet and then perform rest of the operation. :Just add following condition at the very first line of recursive function.
if(visited.contains(s))
return;
add value into "visited" structure right before the For loop.

[sabyasachighosh]

NICE AND EASY EXPLANATION OF THIS HARD QUESTION

[mohitsingla]

Great explanation, @Pepcoding you can add time and space complexity as well in the video for more details.

[ishwarjha]

For TLE leetcode just add a check if the set contains the string as Visited set.
private void removeUtil(String s, int mr, List<String> ans, HashSet<String> set) {

if(set.contains(s)) {
return;
}
set.add(s);
if(mr == 0 && getMin(s) == 0) {
ans.add(s);
}
for(int i=0; i<s.length(); i++) {
if(s.charAt(i) == ')' || s.charAt(i) == '(') {
String l = s.substring(0, i);
String r = s.substring(i+1);
removeUtil(l+r, mr-1, ans, set);
}
}
}

[softpawcreation]

Thanks for the Video and the explanation. Just to add you can also modify the getMin() to calculate min without a stack as follows -

private int getMin(String s) {

int left =0;
int right = 0;

for (int i=0;i<s.length();i++) {
char ch = s.charAt(i);
if (ch == '(') {
left++;
} else if (ch == ')') {
if (left > 0) left--;
else right++;
}
}

return left+right;
}

[atul]

For Those getting TLE exception, just add a check in method to not visit same string twice as below and it will pass :
void getValids(String s, Set<String> set, int mr){

if(visited.contains(s)) return;
visited.add(s);
if( mr == 0 ) {
int now = getMinRemoval(s);
if( now == 0){
set.add(s);
}
return;
}


for( int i = 0 ; i < s.length() ; i++){
continue;
String left = s.substring(0, i);
String right = s.substring(i+1);
getValids(left+right, set, mr-1);

}
}

[Elon-musk-]

Sir this code gives TLE on platform (C++)

[abhinavgupta]

bhiya iska koi optimised solution h kya ..kyuki agar worst case le hum to ye 11 length se upar wali string ke liye TLE de rha h

[Invincible-vpzt]

Tried this solution, it works on IDE but leetcode shall give TLE.

[harshsingh]

Your backtracing algorithm approach is one of the best

[PankajKP]

Sir hum isko is way me kr skte hain? jaise har recursive call me hum current index i include(not remove, k) or not include(remove, k-1)??

[sarveshkaushal]

Sir ji- sab kuchh bhool jaye, chahe Gajani ban jaye, but str.subtring(0, i) and str.substring(i+1) kabhi nahi bhool sakta. Aap har question me substring() pe itna zor lagate ho.Thanks another great video.

[abhi-shake]

Sir if possible try to upload atleast 5 videos a day..It would be a great help to us. Loving these videos🔥

[KaustubhPande]

Nicely explained. Thank you. But, the runtime is quite high. It exceeds the time limit on Leetcode.

[Ankit-hsnb]

class Solution:
def removeInvalidParentheses(self, s):

level = {s}
print(level)
while True:
valid = []
for elem in level:
print(elem)
if self.isValid(elem):
valid.append(elem)
if valid:
return valid
# initialize an empty set
new_level = set()
# BFS
for elem in level:
for i in range(len(elem)):
new_level.add(elem[:i] + elem[i + 1:])
level = new_level

def isValid(self, s):
count = 0
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return count == 0

[noobCoder]

thanks for the soln and explaination sir . I just want to ask whats the time complexity of the soln ?

[mumbaivlog]

Lol muje bhi height ki spelling 30 saal mai yaad hui hai ... awesome channel, awesome content.