Valid parenthesis string | Leetcode

This video explains a very important stack interview coding problem which is to find if a given string is valid or invalid in terms of parenthesis. This question is slightly twisted because it has stars in it as well which can be converted to ( or ) or and empty string. I have explained the solution using two stacks which is one of the optimal solution running in linear time O(N). As usual, CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...

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

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

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

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

[@prajwal9610]

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

[@techdose4u]

Thanks :)

[@praveengautam4689]

genius approach of using stacks

[@stith_pragya]

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

[@nandpatel924]

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

[@techdose4u]

😅

[@sridharbattala3077]

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

[@vani3986]

Great explanation with best solution

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

[@molyoxide8358]

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

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

[@RV-qf1iz]

7:56 new word in the dictionary. Well Explained

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

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

[@TheLaidia]

THANK YOU!! You make this problem a lot easier

[@techdose4u]

Welcome

[@bfoot239]

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

[@nabinkumarshaw4474]

easy and better nice explaination

[@darkexodus6404]

Very articulately explained! Thank you!!

[@amiransari1974]

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

[@techdose4u]

Welcome :)

[@25691331]

Great Resource and great solution.

[@techdose4u]

Thanks :)

[@ris_colid325]

Any intuition for the greedy approach?

[@ajy7867]

Loved your explanation

[@anshumansinghrajawat7242]

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

[@ambujverma9287]

very good explanation .... thank you

[@techdose4u]

Welcome :)

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

[@RaviYadav-xg2hy]

Great explanation and approach made it so easy problem !!

[@techdose4u]

Thanks :)

[@ashwanikumar4288]

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

[@azeezsayyad7281]

thanks bro u deserve lot more subscribers

[@techdose4u]

Thanks bro :)

[@ishikajaiswal4735]

thankyou so much! crisp explanation.

[@arijitdey8419]

Great explaination..Thanks a ton sir

[@techdose4u]

Welcome

[@chenghuilee6982]

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

[@techdose4u]

Thanks :)

[@chandrasekharpatra2416]

Thank you finally someone explained it better.

[@techdose4u]

Welcome :)

[@tumul1474]

awesome dude !! you make amazing tutorials

[@techdose4u]

Thanks :)

[@harifrahman8054]

Nice explaination

[@techdose4u]

Thanks :)

[@krishnavamsichinnapareddy]

Superb explanation ❤

[@ashvinkumhar5819]

Thanks bro your explaination is very great.

[@rhondawang2639]

so smart, very clear thank u

[@techdose4u]

Welcome

[@TheKarateKidd]

Great and clear explanation. Thank you!

[@techdose4u]

Welcome

[@satyanarayanmohanty3415]

Brilliant explanation. Thanks a lot.

[@techdose4u]

Welcome :)

[@fullstackacademy8400]

Perfect approach

[@techdose4u]

Thanks

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

[@rajatbudania6181]

Very Well Explained.!

[@techdose4u]

Thanks

[@karthikmadan]

amazing explaination

[@pranayraj7938]

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

[@techdose4u]

Thanks :)

[@ramnathan4236]

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

[@techdose4u]

You must have done mistake somewhere. Recheck.

[@mohituniyal3008]

superb explanation!

[@techdose4u]

Thanks :)

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

[@spk9434]

Good job

[@techdose4u]

Thanks

[@vishalmishra1937]

supeerb explanation

[@techdose4u]

Thanks :)

[@somyasrivastava6315]

What an amazing solution

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

[@uplsove]

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

[@techdose4u]

Welcome :)

[@arjitgautam365]

Well explained. Appreciated!!

[@rishirajpaulchowdhury4163]

Brilliant explanation. Thanks!!!

[@StockWithSayee]

Loving your teaching :)))

[@piercef7343]

Fantastic explanation!

[@techdose4u]

Thanks :)

[@retrogame3138]

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

[@techdose4u]

Hope it comes true someday 😅

[@ujjvalcodes3629]

Wonderful solution!!

[@weihua5305]

Thank you very much

[@techdose4u]

Welcome :)

[@subhabera5775]

Very good explanation.. earned my subscription

[@techdose4u]

Thanks :)

[@ApnaVlogs-tj7do]

nice explanation

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

[@mrinmoyhalder7293]

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

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

[@sumengwang8918]

Very helpful, Thank you very much!

[@techdose4u]

Welcome :)

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

[@upharrastogi3464]

Great Explanation Surya :)

[@techdose4u]

Thanks

[@rishi3308]

Thanks a lot 😊

[@techdose4u]

Welcome

[@humansofcrypto9746]

Awesome soln!

[@techdose4u]

Thanks :)

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

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

[@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; } }

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

[@rajeshbammidy180]

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

[@techdose4u]

Share your code to get help.

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

[@ANANDJULU]

Thanks , liked and subscribed :)

[@techdose4u]

Welcome :)

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

[@divakaram-xy6si]

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

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

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

[@techgianttechyforever]

Thanks bro

[@techdose4u]

Welcome

[@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; }

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

[@sauravchandra10]

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

[@keerthi442]

Your really awesome bro

[@techdose4u]

Thanks :)

[@AkshayKumar-nh9nh]

Beautiful!

[@techdose4u]

Thanks

[@sharathnagendra3318]

Thank you :D

[@techdose4u]

Welcome

[@s1mple965]

thanks!!

[@techdose4u]

Welcome

[@tanmayshishodia1507]

Great explanation! Kudosss :)

[@techdose4u]

Thanks :)

[@ramsankar585]

Bro i did it with recursion and it passed 38 test cases and got TLE. can i add memoization in it? I want to solve in this approach.

[@techdose4u]

Yes. If you add memoization then it should pass.

[@ramsankar585]

Bro i think this is backtracking problem if we solve with recursion. I am little confused whethet we can add memo or not ..

[@techdose4u]

You can obviously add.....you should make 3 way call on seeing star and one way call on seeing opening or closing bracket.

[@ramsankar585]

Thanks bro. The way u explain makes complicated things much easier. You deserve more subs ❤

[@techdose4u]

I hope our community will grow soon :)

[@sanjeevkumar-wm4mn]

Awesome

[@reroyallover9169]

thanos khus hua

[@AchintoBanerjee]

Genius

[@techdose4u]

:)

[@ruchi315]

I can't solve any problem like this :(