Longest Valid Parentheses Python Solution

Tested Python solution for LeetCode 32 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 32, Hard. Topics: String, Dynamic Programming, Stack. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 32   # by problem number
lcpy gen -s longest_valid_parentheses   # by problem name

​

Problem

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

​

Examples

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Input: s = ""
Output: 0

​

Constraints

• 0 <= s.length <= 3 * 10^4
• s[i] is '(', or ')'.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(n)
    def longest_valid_parentheses(self, s: str) -> int:
        max_length = 0
        # Stack of indices; seeded with -1 as the last "unmatched" position
        stack: list[int] = [-1]

        for i, char in enumerate(s):
            if char == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    # Unmatched ')', reset the base index
                    stack.append(i)
                else:
                    max_length = max(max_length, i - stack[-1])

        return max_length

​

Complexity

Time	Space
O(n)	O(n)

​

Tags

Grind.