Valid parenthesis string | Leetcode

[@TheMOM00000]

GENIUS. Better than all solutions on leetcode, especially the one posted by them.

[@techdose4u]

Thanks ☺️

[@gautamthakur8581]

Its been 3 years of posting the solution ,, still it is the best

[@meetnikhil719]

That moment when I heard the position of the * is important. Hats off!!

[@techdose4u]

Thanks :)

[@meetnikhil719]

@@techdose4u no, Thank you!!

[@rishabhkumar8029]

Really very good explanation

[@ankurgupta4696]

The moment you said that positions are important i understood the concept and coded your concept without even watching full video thanks for your awesome vidoes.....

[@techdose4u]

😂Nice :)

[@akshatjain6854]

Thanks Bro. I was able to pass 28 test cases out of 50 in Leetcode . The main thing which was frustrating me was how to deal with positions. You made it very simple .

[@techdose4u]

I am happy that you tried to solve yourself :)

[@abishekbaiju1705]

After a lot of time I kind of came close on how to solve this. I tried solutions from neetcode, leetcode. but none of them were making sense. but your solution was so so clear. Thanks a lot. I was able to code the solution by myself.

[@techdose4u]

Nice :)

[@prajwal9610]

That was an excellent explanation of this problem. Thanks for giving examples for all the cases.

[@techdose4u]

Thanks :)

[@traton3063]

thanks for another concise and insightful video. I appreciate the fact that you carefully went through the questions and explain the approach with clear details. Also, quickly go through the code like what you did is perfect because the key is the approach and the algorithm for the problem. Great work! Looking forward to seeing more videos from you buddy!

[@techdose4u]

Thanks :)

[@sridharbattala3077]

This is awesome explanation, even leetcode also doesn't have explanation like this

[@uthrakaruna999]

it's a great explanation and solution , here is the same approach in python (if any one needs) class Solution: def checkValidString(self, s: str) -> bool: opens=[] stars=[] for i in range(len(s)): if s[i]=="(": opens.append(i) elif s[i]==")": if opens: opens.pop() elif stars: stars.pop() else: return False else: stars.append(i) # if open is not empty then it is not balanced if opens: for i in range(len(opens)-1,-1,-1): if not stars or stars.pop()

[@yitingg7942]

Yeah!!! Got another right following your video Sir. You just make everything that had been haunting me to go away so easily. Thank god that you are here with me!!

[@techdose4u]

❤️ Keep going

[@molyoxide8358]

You've made this question clear with enough examples than leetcode. thanks for that.

[@praveengautam4689]

genius approach of using stacks

[@ehsona1827]

explanation is top notch, I have solved a similar problem to this problem. The best solution I've come up with is by doing 2 linear passes from left side and then from right side. O(n) time, O(1) space.

[@techdose4u]

Nice....can you please share your code here?

[@surbhi191]

@@techdose4u int count = 0; for(int i = 0; i=0; i--){ char c = s.charAt(i); if(c==')' || c=='*') count++; else{ if(count==0) return false; count--; } } return true;

[@nandpatel924]

100 percent faster, my god i was shocked , really shocked

[@techdose4u]

😅

[@vani3986]

Great explanation with best solution

[@stith_pragya]

Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@bfoot239]

Great job man! This solution is much clear and even better for me to understand the problem than the leetcode editorial solutions

[@thakuranujbhati1565]

Such a master of explanation ❤❤ that any one can easily understand the problem

[@crimsoncad3230]

1 optimization can be done here. After processing closing brackets if len(openStack) > len(star): Return False Else Process openStack from right to left

[@techdose4u]

I think finding the length will again take O(N) if starts counting the element. But if counting takes O(1) than its good. Glad that you noticed. I saw it while editing 😅

[@crimsoncad3230]

@@techdose4uDon't know about other languages but in Python the time complexity to find the length of a list(in this case stack) is O(1). So this optimization can be beneficial.

[@crimsoncad3230]

@@techdose4u We can also have a counter that manages the count of element in the stack after every push and pop operation.

[@techdose4u]

Yea.....it will be great :)

[@techdose4u]

This sounds better :) Works for all languages ;)

[@RV-qf1iz]

7:56 new word in the dictionary. Well Explained

[@chenghuilee6982]

Thank you sir! Very detailed explanation. You deserve more subs .

[@techdose4u]

Thanks :)

[@TheLaidia]

THANK YOU!! You make this problem a lot easier

[@techdose4u]

Welcome

[@azeezsayyad7281]

thanks bro u deserve lot more subscribers

[@techdose4u]

Thanks bro :)

[@hortsss]

Thanks for your explanation! At first I didn't understand every possibilities the '*' had. And also, would never think about doing it using stacks. Congrats, man!

[@techdose4u]

Thanks :)

[@anshumansinghrajawat7242]

Nice explanation brother , keep uploading leetcode videos as much as possible

[@darkexodus6404]

Very articulately explained! Thank you!!

[@pranayraj7938]

Such a good explanation......you deserve more subscribers bro.

[@techdose4u]

Thanks :)

[@chandrasekharpatra2416]

Thank you finally someone explained it better.

[@techdose4u]

Welcome :)

[@tumul1474]

awesome dude !! you make amazing tutorials

[@techdose4u]

Thanks :)

[@nabinkumarshaw4474]

easy and better nice explaination

[@amiransari1974]

this video is very much helpful to understand the problem, Thanks

[@techdose4u]

Welcome :)

[@subhabera5775]

Very good explanation.. earned my subscription

[@techdose4u]

Thanks :)

[@retrogame3138]

Very nice you regularly upload the video soon you have more than 100 k subscriber

[@techdose4u]

Hope it comes true someday 😅

[@ajy7867]

Loved your explanation

[@RaviYadav-xg2hy]

Great explanation and approach made it so easy problem !!

[@techdose4u]

Thanks :)

[@ris_colid325]

Any intuition for the greedy approach?

[@ianpan0102]

Great detailed solution! Except I have one minor issue: From around 5:00 - 5:20, we are trying to balance out the last closing parenthesis at position 6. We see that open_stack is empty, so we aim for the star_stack. According to your explanation, we would pop the star at index 4 to be converted to an open parenthesis and match it with closing parenthesis #6. But intuitively when looking at the string, we should have used the star at index 0 as an open parenthesis for closing paren #6 -- because the star at index 4 should really be a opening match for the closing parenthesis at index 5. Doesn't this matter?

[@techdose4u]

Actually think the other way. I said the last star is popped to match current closing bracket because you convert last star to opening bracket and ignore other brackets, the entire parenthis gets balanced. I said that meaning to take care of current imbalance due to an extra closing bracket. This doesn't mean that inner bracket will balance outer bracket. I hope you got it :)

[@ianpan0102]

@@techdose4u I think I got it. Btw, I came across another method that keeps track of the balance and loop through left to right then right to left. Time complexity is O(2n) = O(n). Here's a sample C++ code I wrote, thought you'd be interested: """"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" class Solution { public: bool checkValidString(string s) { int n = (int)s.length(); int bal = 0; // keep track of balance for (int i = 0; i < n; ++i) { if (s[i] == '(' || s[i] == '*') { bal++; } else { bal--; if (bal < 0) return false; } } bal = 0; // keep track of balance for (int i = n - 1; i >= 0; --i) { if (s[i] == ')' || s[i] == '*') { bal++; } else { bal--; if (bal < 0) return false; } } return true; } }; """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

[@techdose4u]

Nice...thanks

[@25691331]

Great Resource and great solution.

[@techdose4u]

Thanks :)

[@ishikajaiswal4735]

thankyou so much! crisp explanation.

[@ashwanikumar4288]

Nice work! Have you covered the O(1) space solution as well in any other video?

[@ashvinkumhar5819]

Thanks bro your explaination is very great.

[@uplsove]

great explanation bro. this helped me a lot to understand this problem. Thank you

[@techdose4u]

Welcome :)

[@ramnathan4236]

Thank you Sir.I tried using stack but only few testcases passed.

[@techdose4u]

You must have done mistake somewhere. Recheck.

[@krishnavamsichinnapareddy]

Superb explanation ❤

[@harifrahman8054]

Will be helpful if u try to explain all the complex problems on leetcode

[@techdose4u]

I picked leetcode just because of this April challenge. I will further include problems from here in future.

[@arijitdey8419]

Great explaination..Thanks a ton sir

[@techdose4u]

Welcome

[@ambujverma9287]

very good explanation .... thank you

[@techdose4u]

Welcome :)

[@TheKarateKidd]

Great and clear explanation. Thank you!

[@techdose4u]

Welcome

[@harifrahman8054]

Nice explaination

[@techdose4u]

Thanks :)

[@rhondawang2639]

so smart, very clear thank u

[@techdose4u]

Welcome

[@karthikmadan]

amazing explaination

[@StockWithSayee]

Loving your teaching :)))

[@rajatbudania6181]

Very Well Explained.!

[@techdose4u]

Thanks

[@manishnegi7926]

thanks brother i was able to pass only 42 test cases. can you please make a video i.e related to how ur coding is too good ? and how u are able to solve the questions.

[@techdose4u]

I will make it later....but for now I am focussing on study material content itself. 😅

[@satyanarayanmohanty3415]

Brilliant explanation. Thanks a lot.

[@techdose4u]

Welcome :)

[@somyasrivastava6315]

What an amazing solution

[@arjitgautam365]

Well explained. Appreciated!!

[@upharrastogi3464]

Great Explanation Surya :)

[@techdose4u]

Thanks

[@fullstackacademy8400]

Perfect approach

[@techdose4u]

Thanks

[@rishirajpaulchowdhury4163]

Brilliant explanation. Thanks!!!

[@chandankumarnayak7406]

class Solution { public boolean checkValidString(final String s) { int low = 0; int high = 0; for (final char c : s.toCharArray()) { switch (c) { case '(': ++low; ++high; break; case ')': low = Math.max(0, --low); --high; break; case '*': low = Math.max(0, --low); ++high; break; } if (high < 0) return false; } return low == 0; } }

[@mohituniyal3008]

superb explanation!

[@techdose4u]

Thanks :)

[@spk9434]

Good job

[@techdose4u]

Thanks

[@ujjvalcodes3629]

Wonderful solution!!

[@borat_trades2860]

i start to suspect that being good at these problems is a 2 step process: 1)SEEING many problems solutions, understanding them, memorizing them , 2) recalling solutions or TECHNIQUES when facing similar problems. i understand the solution for this problem now thx u! but how am i supposed to know it's 2 stacks?! i suspect i simply need to see many many solutions and then i will be able to know how to solve similar problems.. am i right?!

[@techdose4u]

Actually you are partially correct. If you have experience then obviously many techniques will immediately come to your mind. But the most important thing about programming is to list down the requirement of the question that is the goal. After that you need to think what operations you would do as a straight forward process. Now you think how to achieve a given work in a shorter time. In this case, according to the unsaid requirement of the question, you needed to maintain postion of brackets and stars. This was an extremely important observation and everyone gets it sooner or later. So solving a question elegantly is all about Observations and experience :)

[@mrinmoyhalder7293]

thanks a lot..is this qsn has been asked in any interview ?

[@amanpandey4550]

Another approch - without using extra space' C++ Code- bool checkValidString(string s) { int maxDiff=0; int minDiff=0; for(auto ch : s){ maxDiff+=(ch=='(' || ch=='*') ? 1 : -1; minDiff+=(ch==')' || ch=='*') ? -1 : 1; if (maxDiff < 0) return false; minDiff = max(0, minDiff); } return minDiff==0; }

[@ApnaVlogs-tj7do]

nice explanation

[@piercef7343]

Fantastic explanation!

[@techdose4u]

Thanks :)

[@vishalmishra1937]

supeerb explanation

[@techdose4u]

Thanks :)

[@himanshuchhikara4918]

amazing explanation

[@uditagrawal6603]

I took the greedy approach: public boolean checkValidString(String s) { //Left pass int balance = 0; for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == ')')balance--; else balance++; if(balance < 0)return false; } if(balance == 0)return true; balance = 0; //Right pass for(int i = s.length()-1;i >=0;i--){ if(s.charAt(i) == '(')balance--; else balance++; if(balance < 0)return false; } return true; } Ideology : Left pass : If total sum of ( and * is less then ) then string can never be balanced. Right pass : If total sum of ) and * is less then ( then string can never be balanced.

[@rajeshbammidy180]

I tried using One Stack but my approach fails when we have start in bwn the "(" & ")"

[@techdose4u]

Share your code to get help.

[@ANANDJULU]

Thanks , liked and subscribed :)

[@techdose4u]

Welcome :)

[@sumengwang8918]

Very helpful, Thank you very much!

[@techdose4u]

Welcome :)

[@rogiervdw]

Excellent explanation, thank you! Any chance you can explain the dynamic programming solution that's on LC?

[@techdose4u]

If you have doubts then ask it. I don't have time now to make video for DP. Try solving and ask if you get stuck. You will get help.

[@sauravchandra10]

Did anyone code the greedy approach which takes o(1) space?

[@LTT_VKR]

I am still confused or I don't know how to find the complexity precisely...can you help with that or recommend any videos to watch on that...

[@techdose4u]

Don't think time. Think how many computations you will you do. I have uploaded some basic time complexity videos. You can find blogs on geeksforgeeks as well.

[@LTT_VKR]

@@techdose4u okay 👍

[@humansofcrypto9746]

Awesome soln!

[@techdose4u]

Thanks :)

[@f3-faithfitnessfinance]

Honestly I didn't get the question I was waiting for your video😂😂

[@techdose4u]

🤣 what's this bro....please try to solve the question first yourself. It will be much more helpful.

[@f3-faithfitnessfinance]

@@techdose4u 😂😂 I know I did for all the previous problems... But for this one...I tried understanding the question...I was like what's going on🙆‍♂️

[@techdose4u]

😅 Then it's okay.

[@hortsss]

same lol

[@krishnkumar2277]

could you refer some good resource of graph or please make a playlist of graph

[@techdose4u]

I will soon start graph. You can refer geeksforgeeks for graph. It has everything you need. Just filter and study.

[@adityasrinivas8044]

Hi Sir , @10:28 , You said that by using Greedy Approach , we can solve this in O(1) extra space . How is this possible ?

[@techdose4u]

The trick for O(1) space is simple. You can easily do it in 2 traversals for better understanding. In first traversal from left to right, balance all closing brackets using opening brackets + stars and 2nd traversal from right left, balance all opening brackets using stars and closing brackets already seen :)

[@SR-we1vl]

Well it was a brilliant solution. But what if the interviewer asks do it in O(1) space!? What to do!?

[@techdose4u]

maybe you can check leetcode discussions.

[@weihua5305]

Thank you very much

[@techdose4u]

Welcome :)

[@divakaram-xy6si]

using pointers to keep track of open , star instead of stack would be a more optimal solution.

[@rishi3308]

Thanks a lot 😊

[@techdose4u]

Welcome

[@arthamsreenivas8858]

Thanks Bro, i was trying with single stack with multiple trials did not work, how can we get 2nd stack idea without reading this solution before actual interview :) ?

[@techdose4u]

You just need to practice. There is no easy way out.

[@xapeuuu]

Do you know if ()() would be a accepted case? I don't see anything against it in the description.

[@techdose4u]

Yes it will be accepted. Its answer will be TRUE. It is a valid string afteral.

[@xapeuuu]

@@techdose4u Thanks. I was not getting over the fact that we are not necessarily matching the parenthesis in the most intuitive way. For instance in the case (*)) which is valid -> (()) we are matching the parenthesis with indexes [0,2] and [1,3]. If we knew that the final string would be (()) we would match them differently [0,3], [1,2]. After getting over that i was able to finally understand why this works :)

[@techdose4u]

Great :)

[@vishnugovindan8550]

Could you shed some light on how this could be achieved in O(1) space if done greedy?

[@techdose4u]

Someone had already posted in COMMENT section using 2 traversals, though not greedy but search it. You will get an easy O(1) space solution.

[@surbhi191]

int count = 0; for(int i = 0; i=0; i--){ char c = s.charAt(i); if(c==')' || c=='*') count++; else{ if(count==0) return false; count--; } } return true;

[@ruchi315]

I can't solve any problem like this :(

[@reroyallover9169]

thanos khus hua

[@keerthi442]

Your really awesome bro

[@techdose4u]

Thanks :)

[@SembeiNorimaki]

8:10 I think this is incorrect: you have to start looking the open stack from the lowest element, otherwise you are compensating the lowest element in the open (0) with the highest in stack (4). You need to compensate the 0 with the lowest element in the stack that is higher than 0 (in this case 1), otherwise you might have elements in the open stack that no longer can be compensated. Imagine another example when you end with open= [0, 5] and stack=[2, 6]. If you compensate the 0 with the 6 you will not be able to compensate the 5 with the 2, but if you compensate the 0 with the 2 then you can compensate the 5 with the 6

[@RaviYadav-xg2hy]

No, it's correct because the top of stack of parenthesis will always have the highest index compared with other stack elements below it....So the highest parenthesis index will take the highest star index to get balanced !!

[@AkshayKumar-nh9nh]

Beautiful!

[@techdose4u]

Thanks

[@tanmayshishodia1507]

Great explanation! Kudosss :)

[@techdose4u]

Thanks :)

[@anandpandey918]

//Using ArrayDeque class for implementating Stack (because Stack class is deprecated in java) (40% Faster) class Solution { public boolean checkValidString(String str) { ArrayDequeopenBracket=new ArrayDeque(); ArrayDequestar=new ArrayDeque(); int n=str.length(); for(int i=0;istar.size()) return false; while(openBracket.isEmpty()==false) { if(star.isEmpty()) return false; else { if(star.peek()>openBracket.peek()) { openBracket.pop(); star.pop(); } else return false; } } return true; } } //Using Array for implementating Stack (100% faster) class Solution { public boolean checkValidString(String str) { int n = str.length(); int[] openBracket = new int[n]; int[] star = new int[n]; int openTop = -1; int starTop = -1; for (int i = 0; i < n; i++) { char ch = str.charAt(i); if (ch == '(') openBracket[++openTop] = i; else if (ch == '*') star[++starTop] = i; else // ch==')' { if (openTop!=-1) openTop--; else { if (starTop!=-1) starTop--; else return false; } } } if((openTop+1)>(starTop+1)) return false; while (openTop !=-1) { if(starTop==-1) return false; if(star[starTop] < openBracket[openTop]) return false; openTop--; starTop--; } return true; } }

[@secondIncomePartTime]

you are gem man :)

[@sharathnagendra3318]

Thank you :D

[@techdose4u]

Welcome

[@sanjeevkumar-wm4mn]

Awesome

[@techgianttechyforever]

Thanks bro

[@techdose4u]

Welcome