Longest Valid Parentheses

The Longest Valid Parentheses problem involves finding the length of the longest well-formed parentheses substring within a given string. This is a common challenge in computer science that can be efficiently solved using a stack data structure.

How it Works

The core idea is to iterate through the string, using a stack to keep track of the indices of opening parentheses and invalid closing parentheses. We initialize a `max_len` variable to zero to store the maximum length found so far, and a stack with a sentinel value of -1. This sentinel acts as a reference point for calculating lengths of valid substrings.

When an opening parenthesis `(` is encountered, its index is pushed onto the stack. This marks it as a potentially unmatched opening parenthesis.

When a closing parenthesis `)` is encountered, the top element is popped from the stack. If the stack becomes empty after popping, it means the current closing parenthesis does not have a matching opening parenthesis within the current valid sequence. In this case, its index is pushed onto the stack to serve as a new base for future length calculations, effectively marking the start of a new potential valid sequence.

If the stack is not empty after popping, it means a valid pair has been found. The length of this valid substring is calculated as the current index minus the index at the top of the stack. `max_len` is then updated if this new length is greater.

algorithm longestValidParentheses(s):
    max_len = 0
    stack = [-1] // Initialize stack with a base index

    for i from 0 to length(s) - 1:
        char = s[i]
        if char == '(': 
            stack.push(i)
        else: // char == ')'
            stack.pop()
            if stack is empty:
                stack.push(i) // Unmatched ')' becomes new base
            else:
                max_len = max(max_len, i - stack.top())

    return max_len

This process continues until the entire string has been traversed. The final `max_len` value represents the length of the longest valid parentheses substring.

Key Takeaways

• A stack is used to store indices of unmatched opening parentheses or the last invalid closing parenthesis.
• A sentinel value (e.g., -1) in the stack helps calculate lengths from the beginning of a valid sequence.
• Upon encountering `(`, its index is pushed onto the stack.
• Upon encountering `)`, an element is popped. If the stack becomes empty, the `)`'s index is pushed as a new base. Otherwise, the length is calculated using the current index and the stack's top element.