Valid Parenthesis String - Leetcode 678 - Python

0:00 - Read the problem
2:40 - Drawing Explanation
11:22 - Coding Explanation

leetcode 678

#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[kyu]

i almost committed a crime trying to solve this problem by myself thanks for helping me not become a felon

[MyTeRyS]

Thanks man, i watched your videos on the subway every day, and it helped me to spend that time studying. I appreciate it and I passed the tests for google, now in team matching!

[countdooku]

About that part where we reset leftMin to 0 if it's negative. Take for example a string that looks like this "(((***". After we have parsed this string our leftMax wil be 6 and our leftMin will be 0 which should return true because we can change every asterisk symbol for a right parenthesis symbol. But if we add another asterisk to that string "(((****" our leftMin will become -1. But in this case it doesn't make any sense for us to turn every asterisk into a right parenthesis because it will make the whole string invalid, that's why we treat one asterisk as an empty string and reset our leftMin to 0. And we don't afraid of a case like this "())" where we also should reset our leftMin because our leftMax will become less than 0 and it will return false.

[johnoh]

"We are never going to recover from this" i spit out the cherry seeds from laughing hahahaha

[jans]

This took a while to fully grasp. No chance I would ever come up with this myself under the pressure of a real interview. That being said tho, now that I do understand it I think this is one of the coolest solutions I’ve ever seen

[ancai]

My two cents on the reset of negative leftMin, basically there're two sources we decrease the values of leftMin:
1. when we meet the ')'
2. encounter '*'.
If we have more than enough of ')' leftMax will become negative, and we will directly return false. However, if we don't return, and we get negative leftMin, which means we get more than enough '*' since we can transform the '*' to an empty string, this is how this -1 to 0 comes.
For eg,
(**

[lakshminarayanannandakumar]

An intuitive explanation: As we progress through the string, our minimum and maximum counts of unmatched left parentheses (`leftmin` and `leftmax`) dynamically change. If the `leftmin` becomes negative, it indicates that we've encountered more right parentheses than the total number of corresponding left parentheses and asterisks seen so far. In such cases, we can revise the previous characters to include an empty space, utilizing the wildcard '*' as an optional left parenthesis. This gives the string another chance to remain valid.

However, if the `leftmax` becomes negative, it signifies an irrecoverable situation. This occurs when, despite using all wildcards as left parentheses, the count of right parentheses exceeds the count of remaining unmatched left parentheses and asterisks. In essence, it means that the string cannot be balanced, rendering it invalid. This approach ensures that the string's validity is continuously monitored and maintained throughout the traversal.

[phanthe]

I have this question today as my daily mission and I struggle a lot using stack with 2 times iterating the stack elements.

Thanks for your video and I have a better solution with straightforward checking the string valid

[NhanSleeptight]

leftMin and leftMax is our possibility range where leftMin is decrease choice, leftMax is increase choice. Since we only care if our leftMin can reach 0, if leftMin < 0, we reset it to 0 to eliminate other invalid possibilities.

[ngneerin]

For the first time, i didn't understand your explanation

[lukealberts.hastings]

A good explanation for the reason why we need a special resetting work for and only for leftmin can be:

A string can be invalid only if either it contains more left parentheses than right parentheses and vice versa or their positions violate the balance rule.

Leftmax can help us detect all possible violations but one: some left parentheses do not have matching right parentheses. We leave this mission to leftmin.

We traverse the string for the left to the right, and the leftmin is responsible for recording the most possible choices of the right parenthesis. However, a right parenthesis can never match a left one which is right to it.

So, whenever leftmin is less than zero, we will have no other choices apart from considering it(the character we are visiting) not existing and resetting it(leftmin) to zero. By doing that, we assure that we will never match a right parenthesis to a left one which is right to it.

Therefore, upon traversing the string, if leftmin is still larger than zero, we can be certain that there are unmatched left parentheses and return false. We can also be certain that every left parenthesis is matched otherwise, and since all possible 'right parenthesis' violations would have been detected by leftmax during the traversal, if we can finish the traversal, it is certain that every right parenthesis is matched, so it's safe to return true

[ngoquangtrung]

This is the most brilliant solution, the mathematical correcteness of this solution is very clear.

[shashankjoshi]

Just amazing !! Perfect explanation of the thought process involved !!

[bouzie]

This might be one of the most intelligent solutions I've seen. Never in a million years would I have substituted a backtracking approach for a multi-variable tracker

[jhanzaibhumayun]

I'm thinking O(n). You can loop through the array and have a counter that you add 1to if the parenthesis is left and remove 1 if the parenthesis is right. And have a seperate counter for the *. In every interation you check if the parenthesis counter is negative. If it is you make sure that the wildcard counter is bigger than abs(parenthesis counter). And at the last iteration you check if wildcard counter is equal to or bigger than abs(paranthesis counter).

[edwin]

Hey man, thanks for all your effort and congrats on your recent job! I was wondering if you could make a video for Leetcode problem 2115. Find all Possible Recipes? I'm having a hard time trying to understand it. Thanks

[alexshay]

Hi NeetCode, I noticed that this this problem is under "Stack" and the actual code in Java use Stack, but your video explanation is something else. What is preferred?

[VarunMittal-viralmutant]

I was really conflicted about why we reset leftMin whenever we fall below 0, but then convinced myself with this argument:

One way to think about this is we do -1 from leftMin only for ) and *
And while ) is definitive, * can have 3 possible states. We always assume ) and if we are wrong, then it could be either of the other 2
If c == ) and leftMin < 0, that would mean our assumption that previous * was ) is wrong and it could be "" or (
Eg: (*) or (*))
If c == * and leftMin < 0, that would mean our assumption that * was ) is wrong and it must be "" or )

[DavidDLee]

1. Why is the recursive + caching solution O(N^3) 5:20 ? Seems like it would be same as space complexity O(N^2).
2. The greedy approach is not well explained. Why will it return false iff the string is invalid?

[pulkitjain]

To understand this question, first see question without wild card with stack and variable approach then with this use two stacks of asstrick and open bracket then you realise you dont need to remember everyone of index of open braces and asstrick just difference between two top values, and if difference is negative at certain point you never gonna make valid string.