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

[@leetcode7091]

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

[@mohitsingla6604]

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

[@prashanttrivedi6957]

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

[@atul9130]

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 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++){ if(Character.isLetter(s.charAt(i))) continue; String left = s.substring(0, i); String right = s.substring(i+1); getValids(left+right, set, mr-1); } }

[@rohandevaki4349]

still we are getting same TLE error , last expected input ")(((()(y((u()(z()()"

[@jaivishwakarma304]

thamks vro

[@KaustubhPande]

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

[@Pepcoding]

There may be an edge case which might be missing, kindly analyse it once again, you'll find it. If you like our efforts, will you like to write a review about us here - g.page/Pepcoding/review?rc

[@harshitasingh963]

Happened with me too. I tried running it on Jupyter notebook and it works just fine but the time taken is horrendous

[@amitbajpai6265]

Use this code it is only 5% percent faster but passes all the test cases....... class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: def removals(s,stack): for i in s: if(i=="("): stack.append(i) elif(i==")"): if(len(stack)==0 or stack[-1]==")"): stack.append(i) else: stack.pop() return stack rmarr=removals(s,[]) ans=[] def recursion(s,rmarr,idx): if(idx==len(rmarr)): if(len(removals(s,[]))==0): ans.append(s) return for i in range(len(s)): if(s[i]==rmarr[idx]): if(i==0): recursion(s[:i]+s[i+1:],rmarr,idx+1) else: if(s[i]!=s[i-1]): recursion(s[:i]+s[i+1:],rmarr,idx+1) recursion(s,rmarr,0) if(len(ans)==0): ans=[""] return set(ans)

[@Aniadiakh]

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 0) left--; else right++; } } return left+right; }

[@poojajain9935]

this will not work.

[@harshitashekhawat148]

It's working

[@sarveshkaushal4585]

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.

[@Pepcoding]

Haha.. Keep watching and keep learning😊🙏

[@Elon-musk-007]

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

[@mayankjain-901]

I used same approach and it got submitted on leetcode.

[@harshsingh4063]

Your backtracing algorithm approach is one of the best

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here kzbin.infoabout?view_as=subscriber

[@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.

[@shukanshah5159]

Here is the code for reference. public static void solution(String s, int maxRemovalAllowed, Set ans, Set visited ) { if(visited.contains(s)) return; visited.add(s); if(maxRemovalAllowed == 0) { if(getInvalidParentheses(s) == 0) { ans.add(s); } return; } for(int i = 0; i< s.length() ; i++) { String left = s.substring(0,i); String right = s.substring(i+1); solution(left+right, maxRemovalAllowed-1,ans,visited); } }

[@sulthanmogal9692]

Thank u bruh😍😍

[@ishwarjha3633]

For TLE leetcode just add a check if the set contains the string as Visited set. private void removeUtil(String s, int mr, List ans, HashSet set) { if(set.contains(s)) { return; } set.add(s); if(mr == 0 && getMin(s) == 0) { ans.add(s); } for(int i=0; i

[@MohanRaj-vp1zt]

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

[@pratik.784]

Dp solution will not give tle

[@ankushgupta630]

Please discuss the BFS approach too .

[@abhi-shake9309]

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

[@Pepcoding]

beta kal 5 aai thi. aj bhi aaengi

[@ShahidHussain-dh3pg]

Nice explanation.

[@harshvachhani4922]

Great video sir.

[@shoaibalam7855]

My life summed up at 10:14

[@ankitranjan88]

The Best Explanation...Even A Very Beginner Can Understand it.

[@Pepcoding]

Glad you think so! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@prakashshukla3558]

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

[@Pepcoding]

Thank you so much and If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well Something like this Sumeet Malik from Pepcoding is making all his content freely available to the community You can check it out here - www.pepcoding.com/resources / Also, this is the youtube channel - kzbin.infoplaylists?view_as=subscriber

[@abhinavgupta3913]

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

[@mehulbisht9708]

20:49 if someone missed it , here is how the isValid() method was defined. 😂

[@akashmishra5553]

Sir, you are doing a great job. Thank you!

[@Pepcoding]

So nice of you. keep motivating, keep learning and keep loving Pepcoding😊

[@anantbhargava9049]

We can add irrespective if answer is present is hashset or not because hashset will take care of duplicates by default

[@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)??

[@nitinasthana1740]

Great explanation! Cheers. But this is not exactly Leetcode 301. Out there the input can have the alphabets as well. Example input: "(a)())()" Output: "(a)()()", "(a())()"

[@Pepcoding]

Alright, noted.

[@vaibhavdanagariya6250]

same

[@ialgorithms]

Continuing the above discussion: s = "(a)())()" The modification in the getMin function is as follows [Python]: def getMin(self, s): stack = [] for i in s: if i == "(": stack.append(i) elif i == ")": if stack and stack[-1] == '(': stack.pop() else: stack.append(i) return len(stack) But it will give TLE for # s = "((()((s((((()". An optimization is needed which is discussed in other comments.

[@shadab5azhar]

Very well explained

[@noobCoder26]

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

[@VKBMath]

Great teacher

[@Pepcoding]

Glad you think so!

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here kzbin.infoabout?view_as=subscriber For clearing your doubts, you can join our community on telegram t.me/pepcoding

[@Ankit-hs9nb]

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

[@adityaojha2701]

Very well explained!!

[@Pepcoding]

Thankyou beta! I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@thrivewise1]

Salute you, sir, for great content!

[@Pepcoding]

If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@udaykumar555]

Mazaa aaya bhai....awesome

[@Pepcoding]

For better eperience visit on nados.pepcoding.com Also follow us on our Instagram account to stay tuned. instagram.com/pepcoding/

[@bhatnagarcapital]

Sir ek hi dil hai kitni baar jeetoge ❤️

[@Pepcoding]

haha

[@Raj_Patel21]

One Flaw found in the solution: We are removing the character immediately but we also need to keep it and start looking from the next index here is my Python3 code accepted on Leetcode class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: ''' To find Minimum number of characters ''' def findMin(s): st = [] for i in s: if i not in ["(", ")"]: continue if not st: st.append(i) else: if i == ")" and st[-1] == "(": st.pop() else: st.append(i) return len(st) def helper(start_idx, remaining, mask): if remaining == 0: found_str = ''.join([s[i] for i in range(len(mask)) if mask[i] == 1]) # Checking if found string is valid or not if findMin(found_str) == 0: ans.add(found_str) return if start_idx == len(s): return ''' 2 choices remove that character or not Remove -> mask[] = 0 and remaining - 1 Keep -> mask[] = 1 In both cases we advance start_idx by 1 ''' # Skipping characters other than '(' and')' if s[start_idx] in [')', '(']: mask[start_idx] = 0 helper(start_idx + 1, remaining - 1, mask) mask[start_idx] = 1 helper(start_idx + 1, remaining, mask) ans = set() invalid_count = findMin(s) helper(0, invalid_count, [1 for _ in range(len(s))]) return list(ans)

[@rhythmjayee9707]

Got TLE on leetcode for this solution here is the updated code public List removeInvalidParentheses(String s) { List ls=new ArrayList(); int minRemoval=getMinRemovals(s); HashMap set=new HashMap(); getValidAns(s,set,ls,minRemoval); return ls; } public void getValidAns(String s, HashMap set, List ls,int minRemoval){ if(minRemoval==0){ if(getMinRemovals(s)==0){ ls.add(s); } return; } for(int i=0;i

[@mukultaneja7243]

Great explanation sir ! Sir, isn't it becoming too much complex by removing any random "mra" brackets from the string and then again checking if its valid in the base case and then checking if the string exists ? If instead we remove the same type of bracket before it, I think it will become too much optimized, as it will make the correct strings only.

[@Elon-musk-007]

Can please elaborate your idea??

[@AniketYadav-nu3fb]

Leetcode 301 (JAVA SOLUTION - Invalid parentheses) class Solution { public List removeInvalidParentheses(String str) { List ans = new ArrayList(); HashSet hash = new HashSet(); int min_removal = getMin(str); solution(str, min_removal, hash, ans); return ans; } public static void solution(String str, int min_removal_allowed, HashSet hash, List ans){ if(hash.contains(str)){ return; } hash.add(str); if(min_removal_allowed == 0){ int mrn = getMin(str); // min removal now if(mrn == 0){ ans.add(str); } return; } for(int i = 0; i

[@LOVE-kf9xi]

Solution works , but I can't understand ,how? You are not handling alphabets , but still it is getting accepted, how? Do we not need to worry about the alphabets? Please explain🙏

[@curiouswatcher4626]

one of the most iconic lines by sumeet sir : "chala chala sa lag raha hai " . Edit : Great explanation sir .

[@Pepcoding]

Glad to know that you liked the content and thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating, keep learning and keep loving Pepcoding😊

[@sara1khan157]

how about space complexity is it N {for stack } how much for internal stack {used for recursive calls } is it N ??

[@champ121991]

Great.. But whats the time complexity of this?

[@jigarlove2113]

sir aap kha se padhe ye sab. just mind blowing . already completed your recursion video. im in NIT bhopal but your are better than out professor. :)

[@Pepcoding]

The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating and Keep loving😊

[@whitedracarys7613]

Sir foundation ke baad koi book follow kr sakte hai any suggestion?

[@Pepcoding]

yar book se kahin acha hai, aap leetcode, codechef, codeforces karein. ye practical sa kaam hai. books are inferior to actually solving problems

[@sourabhsharma9070]

very nice explaination!

[@Pepcoding]

Glad you liked it!

[@rohanyelpale3365]

maza aagaya :)

[@aparna8338]

Great explanation sir

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like my efforts, I request a review g.page/Pepcoding/review?rc

[@ialgorithms]

Leetcode 301: Python solution class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: ans = set() mra = self.getMin(s) self.solution(s, mra, ans, set()) return list(ans) def solution(self, s, mra, ans, visited): if s in visited: return visited.add(s) if mra == 0: mrnow = self.getMin(s) if mrnow == 0: if s not in ans: ans.add(s) return for i in range(len(s)): left = s[0:i] right = s[i+1:] self.solution(left+right, mra-1, ans, visited) def getMin(self, s): stack = [] for i in s: if i == "(": stack.append(i) elif i == ")": if stack and stack[-1] == '(': stack.pop() else: stack.append(i) return len(stack) # "((()((s((((()"

[@rahulbhatia3075]

Great content

[@Pepcoding]

please share and subscribe

[@SandipsinghParmar-d3h]

💥

[@ghanibhai1630]

i think we can use memoziation approch also

[@ghanibhai1630]

i did it on my own

[@ashwaniponia3817]

Great explanation sir! one suggestion please include the time complexity analysis of the algorithm.

[@Pepcoding]

Hanji, I am missing out on an important thing. Bhool ja rha hun. Karunga isse aage ki videos mei

[@pluviophile762]

sir this solution is giving TLE on leetcode

[@Pepcoding]

Ok ji. I will check

[@rikinjain5309]

Yes true.

[@indraneelsarkar3452]

yes, TLE

[@nishantdehariya5769]

nice sir but giving TLE for long strings leetcode 301

[@mukulkumar9664]

Great Video Sir !!!

[@Pepcoding]

So nice of you. May i request you to post us a reveiw? g.page/Pepcoding/review?rc

[@mukulkumar9664]

@@Pepcoding Done, Please check

[@santoshr15]

Hi, I tried solving this on Leetcode but after 93 test cases it says time limit exceeded. I followed the same approach as explained in the video. Please do advice what can be done. I can share the code if needed. Thanks

[@Ankit-hs9nb]

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

[@RidhiGarg-t5g]

i tried the code in leetcode and it showed time limit exceed. will someone help?

[@himanshuchhikara4918]

sir time complexity kya hogi recursion fn ki

[@learningsarthak5946]

yeh test case kaise pass karenge? Input: s = "(a)())()" Output: ["(a())()","(a)()()"]

[@himanshunegi5228]

if character is coming just continue in for loop.

[@RiteshKumar-nt5sj]

Sir please come back😭😭

[@karnifazil]

Excellent!

[@Pepcoding]

Thank you! Cheers!

[@kartikaymahajan9591]

what is it's time complexity?

[@411_danishranjan9]

sir, isme aapne backtrack to kiya hi nhi. jab ek elment hata kar call lagai, uske baad wo normal ho sake, taaki wo dusri call laga sake, (yeh to aapne kiya hi nhi).

[@swapnildhiman6585]

❤️

[@rohandevaki4349]

this is giving TLE , update your answer

[@PradeepKumarIIITD]

loved it sir...

[@Pepcoding]

Please like share and subscribe as well.

[@aklogisticals40]

getting TLE on leetcode using same code, can anyone help me.

[@444not]

One optimization - no need to check for valid string if it’s already in set.

[@aakashyadav6228]

Sir how is this a backtracking solution ?

[@prashantbisht2219]

If anyone is looking for leetcode solution for the same. class Solution: def backTrack(self, curr , ans, minRemove,visited ): if minRemove == 0 : if self.minPR(curr) == 0: ans.add(curr) return for i in range(len(curr)): if curr[i] not in [ '(',')']: continue l = curr[0:i]+curr[i+1:] if not l in visited : visited.add(l) self.backTrack(curr[0:i]+curr[i+1:],ans,minRemove-1, visited) def minPR(self, s ): left,right = 0,0 for par in s: if par == '(': left += 1 elif par == ')': if left == 0 : right += 1 else: left -= 1 return right+left def removeInvalidParentheses(self, s: str) -> List[str]: ans = set() visited = set() self.backTrack(s,ans, self.minPR(s),visited) return ans if ans else [""]

[@alankruthisaieni2562]

To get out from out of memory error, Keep a visited hashset to keep track of each string traversed so far if it is already traversed return. if(visited.contains(str)){ return; } visited.add(str);

[@goutamsardar8154]

Thank you Alankruthi.

[@loserfruit9663]

Awesome

[@Pepcoding]

Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@muhammadmustafamustafa2442]

what was the concept of hashset in easy wording ???

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@sourabhsharma9070]

sir bs video me ek chiz ki kami hai ki app hmesha complexity ko btana bhul jate ho..it's obvious but it completes the whole explaination structure!

[@ankitamehra5045]

Hi Sourabh sir has told that backtracking has a general formula - levels to the power of options. hope it helps

[@Pepcoding]

hanji. Ab lag rha hai ki sare questions ki redo kaise karoon. Aage se bnaunga

[@shubhamsharma-sf6lx]

@@Pepcoding commnet section me daalke pin krdo , redo krne ki jroorat nhi :)

[@jatinsingh1368]

for removing tle try to use set for checking each and very string wheteher it is valid or not Here is The Code: class Solution { public: string str; vector ans; int clen; // checking the bool isValid(string s) { stack st; int f=1; for(int i=0;s[i];i++) { if(s[i]=='(') st.push(s[i]); else if(s[i]==')') { if(!st.empty()) { if(st.top()=='(') { st.pop(); } else { f=0; break; } } else { f=0; break; } } } if(f==1 && st.size()==0) return true; else return false; } set se; void all(int k,int i,string bw) { if(k==0 && bw.size()==clen) { // if string is repeated then neglect it if(se.find(bw)!=se.end()) return; else se.insert(bw); //cout

[@shubhramishra4568]

Java Solution accepted on leetcode class Solution { List result= new ArrayList(); HashSet visited; public List removeInvalidParentheses(String s) { if(s.length() ==0){ return result; } visited = new HashSet(); int mra = findInvalidRemoval(s); getValidList(s,mra); return result; } public void getValidList(String s,int minRemoval){ if(visited.contains(s)){ return ; } visited.add(s); if(minRemoval == 0){ //check string formed is valid int valid = findInvalidRemoval(s); if(valid == 0){ result.add(s); } return ; } for(int i=0;i

[@mrmcyx8283]

Thanks a lot

[@deepali-e6f]

Thanks :)

[@mrprime557]

Good explanation, but not the most optimized solution. Getting TLE on leetcode

[@Pepcoding]

Glad to know that you like our explanation. Visit - nados.pepcoding.com and sign up to NADOS. For structured content and better experience. Don't forget to follow us on Instagram instagram.com/pepcoding/

[@ghanibhai1630]

just find opening and closing bracket count and if (>) then (-) if )>( then )-(

[@sara1khan157]

time complexity : N* 2^N ??

[@rajatverma1888]

public class RemoveInvalidParenthesis { private static int getMin(String str) { Stack st=new Stack(); for(int i=0;i

[@jatinbhatoya8420]

your solutionis giving tle on leetcode

[@Pepcoding]

leetcode ki alag playlist bna rhe hain yar.

[@vanditkhuranapvt]

Sir TLE kaise resolve karein iski?

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.

[@psettii]

Please use the below solution class Solution { List result = new ArrayList(); Set set1 = new HashSet(); public List removeInvalidParentheses(String s) { int minRemovals = getMinRemoval(s); System.out.println(minRemovals); Set set = new HashSet(); removeInvalidParenthesesRecursion(s, minRemovals, set); return result; } private void removeInvalidParenthesesRecursion(String s, int min, Set set){ if(min == 0){ int minRemovalAllowed = getMinRemoval(s); if(minRemovalAllowed == 0){ if(!set.contains(s)){ set.add(s); result.add(s); } } return; } for(int i = 0; i < s.length(); i++){ String left = s.substring(0, i); String right = s.substring(i+1); if(!set1.contains(left+right)){ set1.add(left+right); removeInvalidParenthesesRecursion(left+right , min - 1, set); } } } private int getMinRemoval(String str){ Stack stack = new Stack(); for(int i = 0; i < str.length(); i++ ){ char currentChar = str.charAt(i); if(currentChar == '('){ stack.push(currentChar); } if(currentChar == ')'){ if(!stack.isEmpty() && stack.peek() == '('){ stack.pop(); } else { stack.push(')'); } } } return stack.size(); } }

[@ankursuri3853]

@@psettii Thanks for the solution!

[@shubhamsharma-sf6lx]

Sir please please parallel 2-3 dp ki super mast questions daaldo.

[@Pepcoding]

As soon as possible

[@lakshrustagi507]

cpp solution without tle::: i have done an optimisation to cut down rechecking of similar subproblem by using a map. class Solution { public: vector ans; unordered_map map; int get_min(string s) { stack st; for (int i = 0; i < s.size(); i++) { if (s[i] == '(')st.push('('); else if (s[i] == ')') { if (st.size()) { if (st.top() == '(') { st.pop(); } else { st.push(')'); } } else { st.push(')'); } } } return st.size(); } void solve2(string s,int minimum_removal_allowed) { if(map[s]!=0)//for checking that string is already exist in map or not return; else map[s]++; if(minimum_removal_allowed==0) { int minimum_removal_now=get_min(s); if(minimum_removal_now==0) { ans.push_back(s); } return; } for(int i=0;i

[@Pepcoding]

Post your queries on Community post of nados.io Our mentors and alumni will guide you and help you out.

[@ioftheneedle]

mast explanation, lol @ character and which

[@Pepcoding]

Keep learning beta

[@ioftheneedle]

@@Pepcoding ji Prabhu ji

[@code7434]

PLease add Median of Two Sorted Arrays

[@Pepcoding]

Ji jaroor. Jaldi he

[@vaibhavdanagariya6250]

Sir

[@Pepcoding]

Hanji

[@shubhamrawat7895]

Noice.

[@Pepcoding]

acknowledgement

[@adwaitkulkarni]

TLE on leetcode

[@ecea009abhishekshyam8]

sir dont

[@loserfruit9663]

Wchich

[@sciphilo754]

Amazing content!!

[@Pepcoding]

Glad you enjoyed it