Valid Parenthesis String - Leetcode 678 - Python 

Python Code: github.com/neetcode-gh/leetcode/blob/main/678-Valid-Parenthesis-String.py

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

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!

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.

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, (**

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

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.

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

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

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

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

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.

i love you daddy neetcode

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

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 )

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

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.

this question should be hard, not medium

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?

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?

Think of it this way… If you have oversupply of ‘(‘ then you cannot get 0 leftMin value even if you turn all ‘*’ into ‘)’, thats what we did by subtracting 1 from leftMin when we see a ‘*’ If we have oversupply of ‘)’ at any point i in the string then we can’t have a solution even if we turn all ‘*’ into ‘(‘ before point i… that’s where leftMax turns negative If we don’t have oversupply of either ‘(‘ or ‘)’ then we can guarantee that we have a solution

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

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

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

Try to understand the greedy idea for hours but it does not work for me intuitively. So I come back to the 2 stacks solution. Thanks for the explanation. I have been using your Neetcode 150 every day since a month ago. Thanks a lot!

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

if(leftMax < 0 ) return false; // even we selected * as ( still right parenthesis are more then left parenthesis f(leftMin

dude how you got this code . that was beautiful . but how would a beginner would get these thoughts ?

"we will never recover from this" - yes we will never recover from the trauma this question causes

isn't the memoization (dp) solution supposed to be O(N^2) time comp? since we are filling a 2d array of at most size n*n ? this is my solution: (simplified the syntax for non c++ users) bool checkValidString(string s) { int n = s.size(); map dp; // i for index, op means number of opened parenthesis (lrft) bool dfs = (int i, int op){ if(dp.find({i, op})) return dp[{i, op}]; if(op < 0) return false; if(i == n) return op == 0; bool res = false; if(s[i] == '(' ) res = dfs(i+1, op+1); else if(s[i] == ')' ) res = dfs(i+1, op-1); else res = dfs(i+1, op+1) || dfs(i+1, op) || dfs(i+1, op-1); return dp[{i, op}] = res; }; return dfs(0,0); }

DFS is king. Crystal clear logic. Solved in 25ms.

watched a minute because i thought the question will be hell to solve and I didnt wanna keep duct-taping my solutions but I am glad I stopped and did it myself and it was easier than expected.

Just watching the first 2 min of your video, enabled me to solve the problem in a few minutes. I appreciate you setting up the problem coherently, instead of just immediately giving the answer.

nice approach! thanks!

Great solution 👍👍

there is even a simpler greedy approach using O(n) space for a Stack ''' public class Solution { // Time = Space = O(n) Soln public bool CheckValidString(string s) { Stack open = new Stack(), star = new Stack(); for(int i=0;i0) open.Pop(); else if(star.Count>0) star.Pop(); else return false; while(open.Count>0) if(star.Count==0 || star.Pop() < open.Pop()) return false; return true; } } '''

Thanks!

Some questions are not meant to start your day with

In the dp with memo solution, I can't understand why we would revisit the same place. In each call, we always increment the i position, in "dps(i+1,...)", so wouldn't we always have different i in the next recursive call, so never will have it in the cache? Only if we decrement i, "dps(i-1,....)" I would think then we might see it already in the cache. What am I missing?

I tried solving this with DP, there's no way I'd come up with the greedy solution in an interview myself LOL

An easier solution would be to use two stacks.

Great video

class Solution: def checkValidString(self, s: str) -> bool: c = 0 q = 0 for i in range(len(s)): if s[i] == '*': q += 1 elif s[i] == '(': c += 1 else: if c > 0 : c -= 1 elif q > 0: q -= 1 else: return False c = 0 q = 0 for i in range(len(s)-1, -1, -1): if s[i] == '*': q += 1 elif s[i] == ')': c += 1 else: if c > 0: c -= 1 elif q > 0: q -= 1 else: return False return True

Jesus, this is a tough one.

Can anybody explain why the dp solution for this takes o(n^3) ?

please make a video on Find the Closest Palindrome

Couldn't find the link for the DP or memorization solution, can anyone please let me know where I can find it?

Well looks like the greedy solution is not for me lol

really good explanation! thank you

You have already uploaded a video of this problem (same kind)

You didn't explain what would happen if we take the * as an empty string when explaining the greedy method.

I will just go with 2 Stack solution :P

lol, this greedy is tuff to come in interviews

The reason we reset the leftMin to 0 when negative is that we can not cancel a future '('. Think about a simple invalid example "*(".

bool solve( int i , int cnt , string &s){ if( i == s.length() ){ return cnt == 0; } bool ans = false; if( s[i] == '('){ ans = solve(i+1 , cnt+1 , s); } else if( s[i] == ')' && cnt-1 >= 0){ ans = solve( i+1 , cnt-1 , s); } else{ bool ans2 = false; if( cnt-1 >= 0 ) { ans2 = solve(i+1 , cnt-1 ,s); } ans = solve(i+1 , cnt+1 , s) || solve(i+1 , cnt , s ) || ans2; } return ans; } bool checkValidString(string s) { return solve( 0 , 0 , s); } this recursive relation is not working i want to know why .........plzzz anybody can help me

i fails to understand why one single counter is not enough for this problem, traverse through the string, increment counter for open parenthesis and decrement it for closed parenthesis, if counter goes negative at any time, means invalid, and if counter didn't reach 0 at the end, invalid, isn't this very simple logic enough for this problem? someone please correct me.

Pls solve the 3rd problem from today's contest.

I came up with an easier solution O(n) space O(1) It requires two passes class Solution { public boolean checkValidString(String s) { int conflicts=0; int resolvers=0; for(int i=0;i0)resolvers--; else return false; } else{ conflicts--; } } else resolvers++; } conflicts=0;resolvers=0; for(int i=s.length()-1;i>=0;i--){ if(s.charAt(i)==')'){ conflicts++; } else if(s.charAt(i)=='('){ if(conflicts==0){ if(resolvers>0)resolvers--; else return false; } else{ conflicts--; } } else resolvers++; } return true; } }

first comment.

very helpful , very clear, to the point with out confusion explain thans 🫂