Valid parenthesis string | Leetcode #678

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

[TheMOM]

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

[meetnikhil]

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

[ankurgupta]

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

[akshatjain]

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 .

[uthrakaruna]

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()<opens[i]:
return False
return True

[prajwal]

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

[traton]

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!

[iamabishekbaiju]

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.

[molyoxide]

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

[ris_colid]

Any intuition for the greedy approach?

[sridharbattala]

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

[coding_hub]

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

[yitingg]

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!!

[ehsona]

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.

[bfoot]

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

[nandpatel]

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

[RV-qfiz]

7:56 new word in the dictionary.
Well Explained

[ianpan]

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?

[darkexodus]

Very articulately explained! Thank you!!

[TheLaidia]

THANK YOU!! You make this problem a lot easier