LeetCode Day 16 - Wildcards Bracket String (I Struggle)

In problem "Valid Parenthesis String", you need to replace characters '*' with opening and closing brackets (or remove them) in order to get a valid bracket sequence. It's the first time when I don't know how to solve a problem and I need to guess, and then think much longer to understand what happened.

Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

#Coding #Programming

[Learner]

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

[ianpan]

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.

[navjot]

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

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

[tuhinmukherjee]

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

[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;

[adityagaykar]

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

[camper]

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

[anuragporwal]

I used two stacks of pair<char, pos> where pos is the index of the character in the string

[GyaneshISHU]

Such an elegant solution to a seemingly complex problem

[barongrmel]

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!

[neloysinha]

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

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

[befrog]

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 😁

[mayukhchanda]

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

[tarekseguir]

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.

[jatinlalwani]

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

[tony]

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!