LeetCode Day 16 - Wildcards Bracket String (I Struggle)

[@Learner010]

It takes lots of guts to say "I struggled" it shows you are such a genuine person

[@winfredj9820]

bcoz he s true genius..

[@Learner010]

@@vk-vz8qo and you are dumb or what? i m just amazed to see that line and whatever i feel i write it down... as simple as it sound..

[@SaidKerimov]

Best video so far among 30-day challenge videos. I learn more in these videos than in the videos where he says "oh I know how to solve this problem" and solves it in a second.

[@LeeNau]

I prefer seeing the struggle because: 1. it helps demonstrate your thought process and iteration through the problem, 2. i feel like less of an idiot when i struggled for an hour and found no solution :)

[@miteshkumar3183]

'Struggled' but still solved it himself, within 30 minutes. That isn't struggling lol.

[@ianpan0102]

Kids, this is why we respect Errichto -- he's a genuine and honest person who doesn't need to prove anything to people.

[@alejnaser]

Hi Errichto, a lecture on such problems would be great indeed.

[@OptimisticForce]

We need it Yes

[@navjot7397]

The first thing that came to my mind when i saw this problem was to imagine what your video solution will be

[@MattYang]

I liked this one pass "range" solution from the LeetCode discussion (not mine), Intuition is: 1. minOpen keeps track of the min # of left parentheses left, maxOpen keeps track of the max # of left parentheses left 2. if maxOpen dips below 0, then clearly it is invalid (using all stars won't save us). If minOpen dips below 0, we reset it to 0 by "using" a star. 3. At the end, minOpen must equal 0. We only used stars to save ourselves, if minOpen > 0 it means we didn't match all the left parantheses. int maxOpen = 0, minOpen = 0; for (char ch : s) { if (leftParantheses) { minOpen++, maxOpen++ } else if (rightParantheses){ minOpen--; maxOpen--; else if (*) { minOpen--; maxOpen++; } if (maxOpen < 0) { return false;} if (minOpen < 0) { minOpen = 0;} } return minOpen == 0;

[@F0RM4T]

I came up with an algorithm that makes either 2 or 4 arithmetic and logical operations (combined) per iteration, excluding the path that returns prematurely. In opposition to this, that makes either 5 or 6 (with the 0 insertion), excluding the path that returns prematurely.

[@tuhinmukherjee8141]

I love how you let us go through your thought process. I'm learning a lot.

[@SaidKerimov]

Best video so far among 30-day challenge videos. I learn more in these videos than in the videos where he says "oh I know how to solve this problem" and solves it in a second.

[@adityagaykar]

Appreciate you showing up your struggle rather than just editing that part out before posting it. It takes courage to do this.

[@camper8650]

i was able to get a solution but the the solution was exponential, so i waited for your video.

[@mayukhchanda5805]

Even with your warning, I watched it from beginning to end. Love to see your approach towards a problem even if it doesn't turn out right. Love your videos 🤩🤩

[@barongrmel3797]

I struggled so bad that I slept thinking about this question, and started questioning what I was doing with life. This video provide a very nice explanation, I am highly thankful to you!

[@neloysinha8098]

14:49 u seen the meme CODE DOESN'T WORK : "WHY THOUGH ??!!" CODE WORKS :" WHY THOUGH ??!!"

[@anuragporwal4664]

I used two stacks of pair where pos is the index of the character in the string

[@jatinlalwani8355]

Appreciate your genuinity. It's hard to find genuine channels these days. Keep it up. Wishing you all the luck for 1M subs.

[@GyaneshISHU]

Such an elegant solution to a seemingly complex problem

[@tarekseguir201]

I'm watching all your series of 30 days LeetCode challenge, and I would like to think you for the effort and for being so humble I really learning a lot here.

[@blancosj]

Congratulations for this video. I tried linear solution first too and I ended up with dp, basically recursion and memoize. Then I finally went to solutions and review the linear solution.

[@befrog57]

I struggled really hard with this one. Took me atleast 1 hour to get accepted 😶 It makes me feel a little better to see you didn't solve it in 5 minutes though 😁

[@ivanp4740]

Xd, it makes me feel a lot and a lot better that i was able to come up with greedy solution faster than errichto :D (but my was using a stack for keeping indexes of a stars, so it was linear space)

[@ronaldabellano5643]

Ivan I thought same but took me an hour to make it work.

[@spank2877]

It took me around the same time... to understand the problem

[@AAAAAA-gj2di]

@@spank2877 😳

[@1098tony]

I really enjoyed this video since it shows the thought process of top programmers such as Errichto when facing challenging problems.

[@Deanin]

"I'm stuck!" Haha, man that was a mood! The number of times I've had that exact reaction is just unreal. Keep up the great work, man. Always appreciate seeing how people react during these moments of uncertainty!

[@algoseekee]

Explanations start at 19:47. That's clear now! Thanks, man!

[@AdamSmith-du6us]

awesome to see you struggle on one! making the rest of us feeling better.

[@NikhilRaghav23]

Please do video explanation for matching parenthesis with different possibilities. And you are such a genuine person to tell that you struggled for this problem.

[@adibhasan8114]

I SOLVED THIS USING A PAIR STACK and A STRING !!! THOUGH YOUR SOLUTION IS SO COOL ERRICHTO !!

[@mohdar2061]

Thanks. I was stuck trying to find a counting/replacing solution. I just couldn't think as deep as you did about the starts and the balance.. Keep it up!

[@rooftoplin327]

Nneed to see the video more than once.Good job Errichto!

[@anybody_y]

Great explanation Errichto, I started with an approach similarly using only balance and stars, but I couldn't solve it (because I never thought of checking from right to left) and past 30 min mark of struggle, I gave up on it and looked for solutions, and most of them looked somewhat different from this approach. Anyway, it's really great to see you solve it using this approach and in a way, it means I started correctly, just didn't finish it correctly.

[@CarrotCakeMake]

I am always amazed at your ability to endure writing a program in a webpage textbox.

[@namanbhayani1016]

I couldn't solve this problem initially and I thought I was too dumb or something. If he's telling "I am stuck", I can now forgive myself :p Thanks for the explanation!!

[@sebastianmestre8971]

I struggled with this one too. At first I tried something with stacks and some ad hoc logic, which didn't really work. Then I found the dp solution. All in all, it took me like 10 minutes.

[@lovvyparhar393]

one approach was to use stacks. First, ignore all the stars and cancel the parenthesis. Then keep the stars at appropriate positions along with the leftover brackets. Then go over this collection cancelling the leftover parenthesis with stars whenever possible. I am not sure why it works but it worked.

[@jahongirrahmonov7323]

Although it is weird, I am glad that you struggled a little 😂 Loving the series. Keep it up!

[@aditya8404]

I really like this video, because it helped me to think like you do, when i come across a problem and i don't have a solution, this was very insightful thank you :)

[@raahelbaig8347]

I feel so proud of the fact that I went through the exact same steps when coming to the same solution. I made the exact same mistakes while solving my solution as well XD XD

[@oldman713]

Please sir we will be really grateful if you make more lectures on parenthesis and their graph-like approach! Thank You!

[@shubhamuniyal2417]

By far the toughest one in 16 days,.. Errichto struggling means i did good if i completed it in 2 hrs. :D

[@sakshisrivastava5596]

I got annoyed while solving this problem and jump to discussion after like 30 mins. I regret that I should have also struggled more. Anyway, this video is really great and inspiring one. More lectures on these type of questions would be beneficial.

[@ammsa7]

There’s also a DP and a single pass greedy algorithm. The single pass one is pretty nice and it’s only few lines of code (no reverse needed). I’m sure people would appreciate if you cover those as well.

[@abdoulayediagne2976]

I used a stack. Whenever you encounter a "(", you add it's index to the stack, and if it is a ")", you pop the stack if it's not empty and replace that bracket and the element at the removed index with "-" (or any other marking character); if it is empty, check if there's a star on it's left, and then replace both of them with "-". Finally, if there's remaining opening brackets, close them with the "*" on their right if it's possible (with the same method). In the end, if there is no remaining brackets on the string, then it's valid.

[@abdoulayediagne2976]

@@guerakun nope it's O(n) time, and O(n) space

[@valcron-1000]

0:15 HARD DISAGREE. I learn A LOT by watching someone else struggle. I can see what they tried first, what problems did they face and their journey to the correct answer. Defeat is the best teacher. Please don't remove the "struggle" part from any video!

[@MikePrice888]

Your solution is intuitive indeed. Thanks

[@HIOLLJ]

This was doing my head in. Thanks for the elegant solution.

[@ahsanulameensabit]

Great explanation....your approach is so helpful...

[@atikshahriaranik5873]

Yes, please make some videos about bracket sequences. And thanks for all your effort BTW.

[@sagarverma7640]

Please cover the generic variants of parenthesis problems (stack, backtrack, DP/greedy etc.) as you mentioned in this lecture like the buy/sell Stocks one you already did previously..... it was really helpful :)

[@PasselivreEdicoes]

There's a really easy to code O(N²) dp solution. Just do dp[i][balance] where transitions is, well, add 1 to balance if you add a '(', subtract one from balance if add a ')' and you can do all three transitions if you add a "*" (go to dp[i+1][balance], dp[i+1][balance-1] or dp[i+1][balance]+1). Answer is dp[n][0]

[@saiswaroop5889]

I used recursion with memoization. I assumed each star can be converted into (empty, '(' or ')' ) and from there explored all scenarios. To reduce time consumed, i added memoization. Solution ran in 0 ms. if(ch=='(') a=a || dfs(li, i+1, c+1); else if(ch==')') a=a || dfs(li, i+1, c-1); else a=a || dfs(li, i+1, c) || dfs(li, i+1, c+1) || dfs(li, i+1, c-1); i = index in the string c = count of brackets ( if open +1, if close -1)

[@rahil_rehan]

And memoisation?

[@saiswaroop5889]

@@rahil_rehan check this codeshare.io/2WRpxY

[@JorgeIbanez713]

Why memoization actually works? What process you do multiple times?

[@sangramjitchakraborty7845]

Each time you found a * you branched into the three possibilities right? So how did you keep track of the no of brackets already explored? And what did you memoize? What are the overlapping subproblems here?

[@MizardXYT]

@@sangramjitchakraborty7845 Overlapping would be when having two or more stars. First star could decrease the balance, and the second could increase the balance. Same state would be achieved if first star would increase the balance, and second star would decrease it.

[@mohitthorat8580]

Hii, I implemented this with 2 stacks(parenthesis and stars). In both stacks I stored their indices. In parenthesis stack I only pushed opening brackets. Then iterated from left to right, false if current character is ')' and stack is empty and no of stars is 0. After that in end if my stack was not empty I converted stars whose indices were greater than opening brackets into closing brackets. If I couldn't do that then false.

[@gladwinrojer273]

Wow....that sounds like a great approach...did it work??

[@mohitthorat8580]

@@gladwinrojer273 Yes

[@NotFound-hy7qb]

Same because its from discussion

[@jetblackjp]

I did the EXACT same thing. Weird lol.

[@nishantdas272]

Hope that you make a video on such kind(parenthesis checker) of problem in future

[@sharinganuser1539]

one of those questions where ur eyes lights up the moment u read it.....but steadly u realise how cumbersome it is

[@Anshul42]

It was really an interesting problem.. and there were so many different kinds of solutions.. from using brute force, to dp, to greedy, to using stacks, greedy, etc.

[@tuhinmukherjee8141]

True. Even using dp, you can optimise the n^3 complexity to an n^2 complexity. But, later I went through the solutions to find out that there is an O(n) approach to this.

[@RaoVenu]

Errichto, is there a link to the follow up bracket sequences videos? When I saw this, I immediately thought of DP but your solution is so much better.

[@liwaiyip1769]

I really learnt a lot from your videos. Thank you!

[@imranariffin2688]

Please do more of such a problem!

[@YashSingh-ir3ec]

+1 for video tutorials like this problem.

[@manmeetsingh1194]

yes, please provide a similar bracket matching problem explanation.

[@thomi5562]

Nice video although you struggled :D I used a two pointer approach to get it working with only one iteration over each character, but the code is quite long and tricky. Your second solution is much shorter and better to understand.

[@ananths5905]

Please make a lecture style video about paranthesis based thinking... would love to see this real soon from you

[@sankalpramesh5478]

Please do make a video on such parenthesis or wherever such a graph is involved, with strategies to come up with a solution.

[@L0Ls0ul]

For me it's interesting that this particular problem was hard for you. I had more problems with earlier problems. I went through the string from front to back checking if number of "(" + "*" was greater or equal to number of ")" at all points. Then I did the same in reversed order while checking it for ")". That was a pretty straightforward O(n) time solution for me.

[@L0Ls0ul]

Update: I see that's what you did in the end as well.

[@Errichto]

But can you explain why it's correct? Why you won't try to change "*" into opening and closing bracket at the same time?

[@L0Ls0ul]

@@Errichto Yes, it's pretty much the same thought process. Going through the string the first time, you know that there are more "(" or "*" at each place in the string than ")", so you can satisfy "more "(" at all points than ")"". Going through the string the second time, you know that there are more ")" or "*" than "(", so you can conclude "more ")" at all points than "("". Hence you can conclude that there is a way to create an equality with stars but you can't tell which star represents which symbol (from the algorithm as it is since it's not constructive).

[@venkateshthirunagiri85]

@@L0Ls0ul can you share your code?

[@ГеоргийМай-т3в]

I did the same thing almost immediately, but wasn't 100% sure it will be correct :| Still don't understand it intuitively

[@hitesh155]

I too struggled for 20 mins 4 time wrong solution, later went on to use two separate stack - one for parentheses and one for count of stars from previous open parentheses

[@vishalchaurasia96]

Errichto tell me some good resources which you use while learning Number Theory for Competitive Programming. I really need your suggestions.

[@FazeelUsmani]

Hey! Errichto, a video lecture on valid paratheses questions would be much appreciated.

[@TarequeMdKhan]

Thanks for keeping the struggle part

[@kabboghosh1853]

what a humble person

[@manjunathvasam4981]

Please upload lectures covering this topic of balancing brackets it would be very very helpful!!!

[@sounishnath513]

hey... how to split string in c++ in real quick if there are multiple delimiters ? for example Abhishek:34848,Mayur:4739,Friends:2949,Yeah:9889 , this is a string, where Mayur is a person name, and 4739 is an integer, and store it for future operation......

[@faridgadzhiev1440]

Hey Errichto, great video, as always! I also solved this in two passes in a similar way, but there's a neat one pass solution. Did you see it? Do you think it's possible (or needed) to find it under time pressure like an interview or a contest?

[@jishnupramod2130]

A series on patterns and bracket matching is very much appreciated :)

[@yashpreetbathla4653]

true CP , admitted that you struggle cheers man!

[@varunmanchanda3972]

Yes please it will be very helpful if you make more videos on topic like balance parentheses.

[@avi0gaur]

Our thought process is bind with stack or balance counter based approch when it comes to check equation correctness. A small tuning of problem disturb that approach. I had to debug me code in IDE to make it. Poor me.

[@ritwik-chakraborty]

Yes erricto need videos on parenthesis balancing graph...

[@nikhilwalmikpawar]

Yes please post a lecture video on this topic.

[@mansuruddinkhan4001]

Lecture on such problem type would be great

[@almuhimen8023]

Things are getting tough in leetcode, I think.

[@barongrmel3797]

Todays is easy.

[@Squirrelschaser]

I thought of backtracking immediately and then got it working. I tried improving it with DP but I chose bad variables to record state, left paren counter and right paren counter, while the correct way for DP would have been a sum (single counter for left parent (+) and right paren (-)), and index. Couldn't figure out the O(N) time and O(1) space solution at all.

[@SaadTaameOfficial]

I think that it is beneficial to do more bracket problems to get exposed to different techniques of solving them.

[@vivekraj1427]

Really need this topic from u do make one. Thanks for the explanation.

[@openworld7585]

I love you Errichto

[@pranaygarg1370]

It would be really helpful if you make a video on bracket sequences.!

[@Damoygames]

By looking to the solution of LeetCode, you can do it also in one pass using left and right integers. Here is their solution: def checkValidString(s): left = 0 right = 0 for c in s: left += 1 if c == '(' else -1 right += 1 if c != ')' else -1 if right < 0: break left = max(left, 0) return left == 0

[@valcron-1000]

I came up with a solution in Haskell. First, I implemented a function that checks if a "parenthesis expresion" is balanced - only '('and ')' characters - using a Stack. Then I added the '*' case: We can consider it a '(' or a ')' or we can just discard it - consider that it was never there in the first place. If I'm not mistaken this is in theory DFS. It's pretty small so I'll share it here: isBalanced :: [Char] -> Bool isBalanced str = go str [] where go (c : cs) stack | c == '(' = go cs (c : stack) -- Push a '(' into the Stack | c == ')' = if not (null stack) && head stack == '(' then go cs (tail stack) -- Keep going only if we can pop a '(' from the Stack else False | c == '*' = -- Special case for the "polymorphic" character go ('(' : cs) stack -- Assume is a '(' and keep going || go (')' : cs) stack -- Assume is a ')' and keep going || go cs stack -- Assume is a "ghost token" - ignore it - and keep going | otherwise = False -- Invalid char go [] stack = null stack -- If no characters left, check that the Stack is empty

[@anubhavkumar3618]

very good explanation of problem :) hats off Can not we use recursion and backtracking on stack of parenthesis to solve the problem?? I got stuck while I was implementing it:(

[@MizardXYT]

My initial approach was to use a set of possible balances. '(' increased all balances, ')' decreased all balances, and '*' added -1, 0, and 1 to all balances simultaneously, growing the set. I later realized all the possible balances where continuous within a range, so I simplified the set to minBalance and maxBalance. int minBalance = 0, maxBalance = 0; foreach (var c in s) { if (c == '(') { minBalance++; maxBalance++; } else if (c == ')') { if (minBalance > 0) minBalance--; if (maxBalance == 0) return false; maxBalance--; } else if (c == '*') { if (minBalance > 0) minBalance--; maxBalance++; } } return minBalance == 0;

[@ShengLUO]

the reverse trick is cool

[@israkulhaquetusher3256]

i have solved it using a pair under stack , my stack looks line stack < pair < char , int > > stack_name

[@dmitrykarpenko2271]

When you go forward, star is considered to be a replacement for '('. Backward - only for ')'. Can you easily prove that the sets of stars used to replace '(' and to replace ')' will not intersect (e.g. we've not used an already used star)? (e.g. "from the contrary" proof might work, but I'm not completely sure)

[@thomashirtz]

Hey! Kinda curious, could you tell what software do you use to draw your schemes ?

[@karanh]

great video!

[@saifshaikh8055]

Hey errichto, can you tell about DP approach for the problem.Thanks for such videos

[@madhurimamondal9756]

Great ! Thanks a lot !

[@PavanKumar-jt5mq]

I could say this is the hardest problem for me until now. 😢

[@robinli4610]

when you do the first loop, it seems that you want to find a opening bracket for every closing bracket(in this case, some '*' would be regarded as '(' ); And when you do the second loop, you want to find a closing bracket for every opening bracket(in this case, some '*' would be regarded as ')' ). And my question is how to prove that a character '*' would not be regarded as '(' and ')' to avoid contradiction in this two loops?

[@ГеоргийМай-т3в]

If we passed from left to right without replacing any * with '(' , then we pass from right to left and change the * without a doubt. Now let's suppose we changed some '*' on the first pass (from left to right), then there is the LAST star (if it is necessary, we change the stars starting from the left) that we changed. We changed it when we met the right bracket. We mentally note the entire prefix including this right bracket - this prefix is a correct parenthesis string. All stars to the end of expression are free. Now, when we go right to the left, we will have some free stars. We will check if it is possible to make a valid parenthesis string with these "free" stars for each step until we meet that noted prefix. if it is possible, we will reach the first member of "mentally noted" prefix - now it is suffix. We know for sure we will not try to change "*" into ')', because this suffix is correct parenthesis string. Please let me know if it is acceptable explanation

[@robinli4610]

@@ГеоргийМай-т3в not clear much about "All stars to the end of expression are free. Now, when we go right to the left, we will have some free stars. We will check if it is possible to make a valid parenthesis string with these "free" stars for each step until we meet that noted prefix. if it is possible, we will reach the first member of "mentally noted" prefix - now it is suffix. We know for sure we will not try to change "*" into ')', because this suffix is correct parenthesis string."

[@ГеоргийМай-т3в]

@@robinli4610there are 3 options right after we finished the walk from the left to the end (first walk). 1) all the '*' were interpreted as '('. This way we have valid parenthesis prefix made of all the '*' : amount of '(' plus amount of '*' is equal to amount of ')' in this prefix. The remaining part of the line has no '*' symbol and every prefix of this part has more or equal '(' than ')'. While going from right to left we will find if the amounts were equal on every step. 2) none of the '*' were interpreted as '('. This case is trivial. 3) some of the '*' were interpreted as '(' . We can assume that all these '*' go in order (starting with first, then second etc.) because there's no point in letting a single or some '*'. This way we can throw this prefix away - prefix, where the amount of '(' plus amount of '*' is equal to amount of ')' . So now we have a suffix made of '(' , '*' , ')', where every prefix of this remaining suffix has more or equal '(' than ')' and all the '*' are "free" - it means we did not use them during the first walk as '(' . So the only thing to check is if on every step in walking from right to left the amount of ')' plus amount of '*' is not less than the amount of ')'.

[@piyushjain5658]

Genuine video

[@PasselivreEdicoes]

Definitely hardest problem so far.

[@MiketheCoder]

Errichto, can you do a vid about people cheating in competitive programming? Apparently a guy named Karan Gujar was cheating on codeforces and google code jam and bragged about his ratings on quora to get fame. Since you obviously worked very hard in competitive programming, what are your thoughts on this?

[@VinayKumar-rq5kd]

Please do videos on this more after this month.

[@yyyooohhhooo]

Lecture on annoying bracket series would be great, Edward Snowden! I meant Errichto...

[@ThomasSheppardPOB]

Hey Erric. At around 15 mins in you reference the array size being between 1,100 and say "DP was a intended solution here" can you explain what DP is?

[@abdoulayediagne2976]

Dynamic Programming. He made some videos on it.