Stack

Longest Valid Parentheses

hard

DESCRIPTION (inspired by Leetcode.com)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. A well-formed parentheses string is one that follows these rules:

• Open brackets must be closed by a matching pair in the correct order.

For example, given the string "(()", the longest valid parentheses substring is "()", which has a length of 2. Another example is the string ")()())", where the longest valid parentheses substring is "()()", which has a length of 4.

Example 1:

Inputs:

s = "())))"

Output:

2

(Explanation: The longest valid parentheses substring is "()")

Example 2:

Inputs:

s = "((()()())"

Output:

8

(Explanation: The longest valid parentheses substring is "(()()())" with a length of 8)

Example 3:

Inputs:

s = ""

Output:

0

Explanation

At a high level, we can solve this problem by iterating over each index of the string, and then calculating the length of the longest valid parentheses substring that ends at that index. We can then take the maximum of these lengths to get the final answer.

Each time we encounter a closing parenthesis ')', it has the potential to close a valid parentheses substring. In order to calculate the length of the longest valid parentheses substring that ends at a given index, we need to know the index of the last unmatched opening parenthesis '('.

The length of the valid substring ending at the current index can be calculated by taking the difference between the current index and the index of the last unmatched opening parenthesis.

Let's visualize a few examples to understand how that calculation works:

1. Initialize a stack. The stack will always contain the index of the last unmatched opening parenthesis, or the "start" of the current valid substring. Initially, the stack will contain -1 as the start of the current valid substring.
2. Each time we encounter an opening parenthesis '(', we'll push its index onto the stack, which represents the index of the last unmatched opening parenthesis.
3. Each time we encounter a closing parenthesis ')', we'll do the following:
   1. We first pop the top element from the stack, as this closing parenthesis has the potential to close a valid parentheses substring.
   2. Now, after popping, there are two possible cases:
      1. The stack is not empty, and the top of the stack represents the index of the last unmatched opening parenthesis. We calculate the length of the valid substring ending at the current index by taking the difference between the current index and the index of the last unmatched opening parenthesis.
      2. The stack is empty. This means that this closing parenthesis was unmatched. We'll update the start of the valid substring to the current index by pushing the current index onto the stack.

Solution

def longest_valid_parentheses(s):
    max_len = 0
    stack = [-1]

for i, char in enumerate(s):
        if char == '(':  
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])

return max_len

Complexity Analysis

Time Complexity: O(n) where n is the length of the input string. We iterate over each character of the string once. At each character, we perform a constant amount of work.

Space Complexity: O(n) where n is the length of the input string. The stack can contain at most n elements (for example, if the input string is '(((((((((((').