LeetCode 32. Longest Valid Parantheses

May 3, 2025

I went through a period of intense study, focusing on solving problems with C++. Now, I'm back to Python and happy to walk through this solution to longest valid parantheses.

1class Solution:
2    def longestValidParentheses(self, s: str) -> int:
3        stack = [-1]
4        max_len = 0
5
6        for i in range(len(s)):
7            if s[i] == '(':
8                stack.append(i)
9            else:
10                stack.pop()
11                if not stack:
12                    stack.append(i)
13                else:
14                    max_len = max(max_len, i - stack[-1])
15        
16        return max_len

Each time we encounter an opening paranthesis, we add its index to our stack. Thus, when we find a closing parenthesis, we pop the stack. This will leave us with the index of the last invalid index, or an empty array (we reached an invalid closing paranthesis). With that index of the last invalid paranthesis, we calculate the max length. This works for this example:

Input: s = ")()"

Output: 2 (correct!)

We can check with a longer example too.

Input: s = ")()()"

Output: 4

The time complexity is O(n) since we step through the array once, and our space complexity is also O(n). We use a stack that can be up to N elements (all opening parantheses).

LeetCode 1004. Max Consecutive Ones III