[00:01] looks impossible until you see what the stack is actually storing. See, you're given a string of parentheses and your goal is to find the length of the longest substring of parentheses. Now, hearing parentheses, your mind probably
[00:13] went to let me store the brackets in the stack. If you do this, you'd build the string, which would be O of N squared complexity. And we can do a lot better storing the brackets or the parentheses in the stack, store their indices.
[00:27] Specifically, the index of the last unmatched opening parenthesis. Let's example. You want to seed the stack with negative one as the base case. Now, index zero is an open bracket. So, push zero to the stack. Index one is also an
[00:41] stack, too. But now, index two is a closed bracket. And so, we pop one from closed bracket. And so, we pop one from the stack. Stack top is now zero and the length equals two minus zero, which is two. So, the current max length is two.
[00:54] Similarly, index three is an open bracket. So, we push three onto the stack. Now, index four is again a closed bracket. So, we can pop that three from the stack. The stack top now again is zero and the length equals four minus
[01:06] zero, which is four. So, the current max length is four. Finally, index five is a closed bracket. So, we can pop zero from the stack. The stack top is now that negative one and the length equals five minus negative one, which is six. So,
[01:19] the current max length is six and that's our final answer. So, the key is that the stack top always marks where the current valid run started, giving you a one pass O of N solution. Learn more with interactive visualizations at
[01:31] hellonerd.com and go ahead and smash that follow button.