32. Longest Valid Parentheses - Detailed Explanation

Problem Statement

You are given a string containing just the characters '(' and ')'. Your task is to find the length of the longest valid (well-formed) parentheses substring.

Example 1

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

Example 2

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

Example 3

• Input: ""
• Output: 0
• Explanation: The string is empty, so there is no valid substring.

Constraints:

• The length of the string is between 0 and a large number (e.g., 30000).
• The string consists only of the characters '(' and ')'.

Hints

1. Stack Hint:
   Think about using a stack to store indices. This can help you determine the start of a valid substring when you encounter a closing parenthesis.

2. Dynamic Programming Hint:
   Consider using a DP array where each element represents the length of the longest valid substring ending at that index. Update this array based on previous computations.

Approaches

Brute Force Approach

• Idea:
  Check every possible substring and verify if it is valid by using a stack or a counter.

• Steps:

  1. Generate all possible substrings.
  2. For each substring, check if it forms a valid parentheses sequence.
  3. Keep track of the maximum valid length found.

• Complexity:

  • Time: O(n³) (O(n²) substrings and O(n) to validate each)
  • Space: O(n) for validation checks
    Not efficient for large inputs.

Dynamic Programming Approach

• Idea:
  Use a DP array where dp[i] represents the length of the longest valid substring ending at index i.

• Steps:

  1. Initialize a DP array of zeros.
  2. Iterate through the string from index 1 to the end.
  3. If s[i] is ')':
     • If s[i-1] is '(', then update:
       dp[i] = (dp[i-2] if i >= 2 else 0) + 2
     • Else if s[i-1] is ')' and the character before the previous valid substring (at index i-dp[i-1]-1) is '(', update:
       dp[i] = dp[i-1] + 2 + (dp[i-dp[i-1]-2] if (i-dp[i-1]) >= 2 else 0)
  4. Update the maximum length encountered.

• Complexity:

  • Time: O(n)
  • Space: O(n)

Stack-Based Approach

• Idea:
  Use a stack to keep track of indices. Push -1 initially to handle edge cases.

• Steps:

  1. Initialize a stack with -1.
  2. Iterate through the string:
     • If the character is '(', push its index onto the stack.
     • If the character is ')', pop the top of the stack.
       • If the stack is empty after popping, push the current index.
       • Else, update the maximum valid length using:
         current_length = current_index - stack.top()
  3. The maximum value encountered during the iteration is the answer.

• Complexity:

  • Time: O(n)
  • Space: O(n)

Two-Pass / Counter Approach

• Idea:
  Use two counters (for left and right parentheses) and scan the string twice—once from left to right and once from right to left.

• Steps (Left-to-Right):

  1. Initialize left = 0 and right = 0.
  2. For each character:
     • Increment left if the character is '('.
     • Increment right if the character is ')'.
     • If left == right, update the maximum length.
     • If right > left, reset both counters.

• Steps (Right-to-Left):

  1. Reset left = 0 and right = 0.
  2. Iterate from the end of the string:
     • Increment counters similarly.
     • If left == right, update the maximum length.
     • If left > right, reset both counters.

• Complexity:

  • Time: O(n)
  • Space: O(1)

Complexity Analysis

• Brute Force:

  • Time: O(n³)
  • Space: O(n)

• Dynamic Programming:

  • Time: O(n)
  • Space: O(n)

• Stack-Based:

  • Time: O(n)
  • Space: O(n)

• Two-Pass / Counter:

  • Time: O(n)
  • Space: O(1)

Python Code