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, (**
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
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.
@@sheikhmkrifat7749 Yeah his explanation is quite nuanced and it took me a while to grasp the optimal solution. Essentially we are walking 2 paths: maximal path and balanced path, where in maximal path we are treating all "*" as "(", and in the balanced path we are transforming "*"s in a way that balances all brackets as much as possible. leftMax keep tracks of num of unclosed "(" in the maximal path, and leftMin keep tracks of the same for balanced path. The whole point of maximal path is to detect unrecoverable state, ex: "*))", that is, if leftMax becomes -1, it means even tho we maximized the number of left brackets by treating all "*" as "(", we will still eventually have an unclosed ")", so at this point as Neetcode said we will never recover because the string will never become valid. The balanced path is why this solution is greedy because for this path we are making the most greedy choice to make the brackets as balanced as possible; whenever we encounter "*" we treat it as ")", and whenever leftMin becomes -1, meaning we have one extra bracket at the end of the current balanced path, we will try to rectify that. The key point is this: if we are not in unrecoverable state, and leftMin becomes -1, then we can rectify the current balanced path so all brackets are balanced, this is because if we are not in unrecoverable state, and the balanced path has an unclosed ")" at the end, then there must exist at least one "*" in ")" or "_" form in the current balanced path (provable), by transforming an existing "*" in ")" form into "_" or an existing "*" in "_" form into "(", the balanced path will have all brackets balanced. This is what "if leftMin < 0: leftMin = 0" is doing.
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 )
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 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
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?
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.
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).
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?
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!
@@prasad9012 Hope this help ``` class Solution: def checkValidString(self, s: str) -> bool: return self.checkValidString_2stacks(s) def checkValidString_2stacks(self, s: str) -> bool: main, star = [], [] for i, c in enumerate(s): if c == "(": main.append(i) continue if c == "*": star.append(i) continue # if we see a right ), try to cancel the left ( if main: main.pop() elif star and star[-1] < i: star.pop() else: return False # If main stack has left parenthesis, try to cancel it with * while main and star and star[-1] > main[-1]: star.pop() main.pop() # If we cannot cancel the left parenthesis if main: return False # as along as the main stack is empty, we do not care the star anymore. return True ```
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.
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
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);
leftMin stores the number of unmatched "(" as we try to manipulate the number of unmatched "(" to 0, by treating "*" as ")" at first encounter, and when leftMin becomes -1, either transform an existing "*" in ")" form to "_", or an existing "*" in "_" form to "(". "if leftMin < 0: leftMin = 0" has the following logic: "if leftMin < 0" executes and is true, then leftMin == -1 and there must be at least one "*" in "_" or ")" form, otherwise leftMin == leftMax == -1 because either there are no "*", or all "*" are in "(" form, and we would've returned False) Case 1: the right most char of curr str is "*", then it is currently in ")" form, simply transform it to "_" and leftMin becomes 0 Case 2: the right most char of curr str is actual ")", then there must be at least one "*" in ")" or "_" form on the left, either transform a "*" in ")" form to "_" or a "*" in "_" form to "(", and leftMin becomes 0 (because everything will be balanced - this may require additional proofs involving non-intersecting/intersecting brackets for more rigor) Example: s = "*))" read "*" -> treat it as ")" -> leftMin == -1 -> transform ")" to "_" -> leftMin == 0 read ")" -> leftMin = -1 -> transform "_" to "(" -> leftMin == 0 read ")"-> leftMin = -1 = leftMax -> return False
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;
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.
I think it is a mistake. I think time complexity is O(N^2) too. The cache size, worst-case is O(N^2) because the worst-case combinations of 'i' and 'left', both bounded by N. NeetCode says each cache entry requires x N, but I don't think this is right. Every invocation simply calls itself again, with no loops, etc.
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?
But you call dfs multiple times for i + 1, right? Also, every one of these invocations will split into more if another * is found. The end result is many calls to the same position and even with the exact same arguments.
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.
That would be the case only if there were no '*' - wild card. The wild card changes the whole game With your method, (*)) will give 'False' but it's actually True since * can be replaced with (
} 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
bro i too had the same intuition , but i lacked at extra opening parenthesis , thanks for the code , now i learnt my mistake class Solution { public boolean checkValidString(String s) { int check = 0; int boost = 0; for(int i =0;i
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
What the heck do you mean!
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!
So happy for you brother!
I need stuff like this to keep me motivated :)
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.
Thanks for explaining, it is really a helpful comment
thanks!
great explanation!
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,
(**
👍
Awesome. Thanks
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.
"We are never going to recover from this" i spit out the cherry seeds from laughing hahahaha
Lol sometimes I get carried away
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
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.
For the first time, i didn't understand your explanation
Lol
First time I felt this way also
I know right. I feel so stuck.
same here
@@sheikhmkrifat7749 Yeah his explanation is quite nuanced and it took me a while to grasp the optimal solution.
Essentially we are walking 2 paths: maximal path and balanced path, where in maximal path we are treating all "*" as "(", and in the balanced path we are transforming "*"s in a way that balances all brackets as much as possible. leftMax keep tracks of num of unclosed "(" in the maximal path, and leftMin keep tracks of the same for balanced path.
The whole point of maximal path is to detect unrecoverable state, ex: "*))", that is, if leftMax becomes -1, it means even tho we maximized the number of left brackets by treating all "*" as "(", we will still eventually have an unclosed ")", so at this point as Neetcode said we will never recover because the string will never become valid.
The balanced path is why this solution is greedy because for this path we are making the most greedy choice to make the brackets as balanced as possible; whenever we encounter "*" we treat it as ")", and whenever leftMin becomes -1, meaning we have one extra bracket at the end of the current balanced path, we will try to rectify that. The key point is this: if we are not in unrecoverable state, and leftMin becomes -1, then we can rectify the current balanced path so all brackets are balanced, this is because if we are not in unrecoverable state, and the balanced path has an unclosed ")" at the end, then there must exist at least one "*" in ")" or "_" form in the current balanced path (provable), by transforming an existing "*" in ")" form into "_" or an existing "*" in "_" form into "(", the balanced path will have all brackets balanced. This is what "if leftMin < 0: leftMin = 0" is doing.
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 )
Simple argument is, at any point of time we can have count(")")
if leftmin goes below negative we remove the possibility of that * being left parenthesis because that entire expression will be invalid
A simpler solution with time complexity = O(n) and space complexity = O(n)
th-cam.com/video/KuE_Cn3xhxI/w-d-xo.html
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
Very helpful, thanks
This is the most brilliant solution, the mathematical correcteness of this solution is very clear.
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
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?
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.
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
this question should be hard, not medium
i love you daddy neetcode
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).
This is incorrect,
We could have ***(((, this would return True, since # wild == # left,
But the position in which we encounter wild cards matters.
I implemented that solution,it failed and then i searched this video LOL
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?
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!
Can you share the 2 stacks solution?
@@prasad9012 Hope this help
```
class Solution:
def checkValidString(self, s: str) -> bool:
return self.checkValidString_2stacks(s)
def checkValidString_2stacks(self, s: str) -> bool:
main, star = [], []
for i, c in enumerate(s):
if c == "(":
main.append(i)
continue
if c == "*":
star.append(i)
continue
# if we see a right ), try to cancel the left (
if main:
main.pop()
elif star and star[-1] < i:
star.pop()
else:
return False
# If main stack has left parenthesis, try to cancel it with *
while main and star and star[-1] > main[-1]:
star.pop()
main.pop()
# If we cannot cancel the left parenthesis
if main:
return False
# as along as the main stack is empty, we do not care the star anymore.
return True
```
@@nguyentp2133 I prefer this.. this is intuitive one
@@nguyentp2133 Thanks for this solution. It's much easier to grasp.
Just amazing !! Perfect explanation of the thought process involved !!
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.
if(leftMax < 0 ) return false;
// even we selected * as ( still right parenthesis are more then left parenthesis
f(leftMin
Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
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);
}
Also the editorial mention O(n^2) for the solution 2d dp with memoization
leftMin stores the number of unmatched "(" as we try to manipulate the number of unmatched "(" to 0, by treating "*" as ")" at first encounter, and when leftMin becomes -1, either transform an existing "*" in ")" form to "_", or an existing "*" in "_" form to "(".
"if leftMin < 0: leftMin = 0" has the following logic:
"if leftMin < 0" executes and is true, then leftMin == -1 and there must be at least one "*" in "_" or ")" form, otherwise leftMin == leftMax == -1 because either there are no "*", or all "*" are in "(" form, and we would've returned False)
Case 1: the right most char of curr str is "*", then it is currently in ")" form, simply transform it to "_" and leftMin becomes 0
Case 2: the right most char of curr str is actual ")", then there must be at least one "*" in ")" or "_" form on the left, either transform a "*" in ")" form to "_" or a "*" in "_" form to "(", and leftMin becomes 0 (because everything will be balanced - this may require additional proofs involving non-intersecting/intersecting brackets for more rigor)
Example: s = "*))"
read "*" -> treat it as ")" -> leftMin == -1 -> transform ")" to "_" -> leftMin == 0
read ")" -> leftMin = -1 -> transform "_" to "(" -> leftMin == 0
read ")"-> leftMin = -1 = leftMax -> return False
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
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;
}
}
'''
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.
Can anybody explain why the dp solution for this takes o(n^3) ?
I think it is a mistake. I think time complexity is O(N^2) too.
The cache size, worst-case is O(N^2) because the worst-case combinations of 'i' and 'left', both bounded by N.
NeetCode says each cache entry requires x N, but I don't think this is right. Every invocation simply calls itself again, with no loops, etc.
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?
But you call dfs multiple times for i + 1, right?
Also, every one of these invocations will split into more if another * is found. The end result is many calls to the same position and even with the exact same arguments.
This is just ... clever!
I tried solving this with DP, there's no way I'd come up with the greedy solution in an interview myself LOL
Some questions are not meant to start your day with
Thanks!
Couldn't find the link for the DP or memorization solution, can anyone please let me know where I can find it?
The editorial for this problem on leetcode has all the solutions
Great video
An easier solution would be to use two stacks.
True however u sacrifice space
isnt a single counter of type int be the even easier solution?
@@arjuntt2604 I think it's relative.
It's more intuitive. I think he's going for a low mem solution here
@@yashpathak9285 i didn't get you,
really good explanation! thank you
please make a video on Find the Closest Palindrome
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.
You didn't explain what would happen if we take the * as an empty string when explaining the greedy method.
Well looks like the greedy solution is not for me lol
You have already uploaded a video of this problem (same kind)
Let him upload two right
I will just go with 2 Stack solution :P
The reason we reset the leftMin to 0 when negative is that we can not cancel a future '('. Think about a simple invalid example "*(".
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.
That would be the case only if there were no '*' - wild card. The wild card changes the whole game
With your method, (*)) will give 'False' but it's actually True since * can be replaced with (
lol, this greedy is tuff to come in interviews
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
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;
}
}
bro i too had the same intuition , but i lacked at extra opening parenthesis , thanks for the code , now i learnt my mistake
class Solution {
public boolean checkValidString(String s) {
int check = 0;
int boost = 0;
for(int i =0;i
@@LOKESHE-wi2yd ohh nice
@@LOKESHE-wi2yd my brain worked really good 5 months ago now I've got brainrott cannot understand my own code
first comment.
very helpful , very clear, to the point with out confusion explain thans 🫂