32. Longest Valid Parentheses

This problem asks to find the length of the longest valid (well-formed) parentheses substring within a given string containing only '(' and ')'.

Approach 1: Dynamic Programming

This approach uses dynamic programming to build a DP array f where f[i] represents the length of the longest valid parentheses substring ending at index i.

Algorithm:

1. Initialization: Create a DP array f of size n+1 (where n is the length of the string) and initialize all elements to 0. This handles edge cases of empty or single-character strings.

2. Iteration: Iterate through the string from index 1 (second character):

   • If the current character s[i-1] is ')', check the previous character s[i-2]:
     • If s[i-2] is '(', it means we found a valid pair "()". The length of the longest valid substring ending at i is f[i] = f[i-2] + 2.
     • If s[i-2] is ')', we need to look further back. Let j = i - f[i-1] - 1. If j is a valid index and s[j-1] is '(', then we found a longer valid substring. The length becomes f[i] = f[i-1] + 2 + f[j-1]. This accounts for potentially nested valid substrings.

3. Result: The maximum value in the f array represents the length of the longest valid parentheses substring.

Time Complexity: O(n) - Single pass through the string. Space Complexity: O(n) - For the DP array f.

Approach 2: Using Stack

This approach utilizes a stack to track the indices of opening parentheses.

Algorithm:

1. Initialization: Initialize a stack stack with -1 (to handle edge cases) and a variable ans to 0 (to store the maximum length).

2. Iteration: Iterate through the string:

   • If the character is '(', push its index onto the stack.
   • If the character is ')', pop an element from the stack.
     • If the stack is empty, it means we encountered a ')' without a matching '('. Push the current index onto the stack to start a new potential substring.
     • Otherwise, the popped index represents the matching '(' for the current ')'. Calculate the length i - stack[-1] (current index minus the index of the matching '(') and update ans if necessary.

3. Result: ans holds the length of the longest valid parentheses substring.

Time Complexity: O(n) - Single pass through the string. Space Complexity: O(n) - In the worst case (all opening parentheses), the stack can store all indices.

Code Examples (Python)

Approach 1 (Dynamic Programming):

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        for i in range(2, n + 1):
            if s[i - 1] == ')':
                if s[i - 2] == '(':
                    f[i] = f[i - 2] + 2
                else:
                    j = i - f[i - 1] - 1
                    if j > 0 and s[j - 1] == '(':
                        f[i] = f[i - 1] + 2 + f[j - 1]
        return max(f)

Approach 2 (Using Stack):

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        ans = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    ans = max(ans, i - stack[-1])
        return ans

Both approaches have the same time and space complexity. The stack-based approach might be slightly easier to understand conceptually for some, while the dynamic programming approach might be preferred by others due to its straightforward iterative nature. The choice depends on personal preference and coding style.