32. Longest Valid Parentheses - Detailed Explanation

Problem Statement

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

Examples:

• Example 1:

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

• Example 2:

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

• Example 3:

  • Input: ""
  • Output: 0
  • Explanation: An empty string has no valid substrings.

Constraints:

• The length of the input string can be zero.
• The string consists only of the characters '(' and ')'.

Hints for the Solution

• Hint 1:
  Think about what makes a parentheses string valid. A valid substring has every opening parenthesis '(' matched with a closing parenthesis ')' in the correct order.

• Hint 2:
  One efficient approach is to use a stack to track the indices of unmatched parentheses. This helps you quickly determine the length of valid segments when a match is found.

Approaches to Solve the Problem

1. Brute Force Approach

Idea:
Check every possible substring and validate if it is a well-formed parentheses string. Then, record the length of the valid ones.

Steps:

• Generate all possible substrings.
• For each substring, check whether it forms a valid sequence.
• Track the maximum length found.

Downside:

• This approach is very inefficient with a time complexity of O(n³) (generating substrings and validating each one), which is not feasible for large inputs.

2. 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 size n (length of the string) with all zeros.
2. Iterate through the string from index 1 to n-1.
3. If the character at i is ')':
   • Case 1: If the previous character is '(', then dp[i] = dp[i-2] + 2.
   • Case 2: If the previous character is also ')' and the character at the position i - dp[i-1] - 1 is '(', then dp[i] = dp[i-1] + 2 plus any valid substring ending before that (i.e. dp[i - dp[i-1] - 2]).
4. Keep track of the maximum value in the DP array.

Complexity:

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

3. Stack-Based Approach

Idea:
Use a stack to store indices of the characters. Begin by pushing -1 onto the stack as a base index. Then iterate over the string and:

• Push the current index if the character is '('.
• For a ')', pop an index from the stack.
  • If the stack becomes empty, push the current index as a new base.
  • Otherwise, calculate the valid substring length as the difference between the current index and the top of the stack.

Steps:

1. Initialize a stack with -1.
2. Loop through the string by index:
   • If s[i] is '(', push i.
   • If s[i] is ')', pop from the stack.
     • If the stack is empty, push i.
     • Otherwise, update the maximum length as i - stack.top().
3. The maximum length recorded is the answer.

Complexity:

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

4. Two-Pointer Approach

Idea:
Use two counters (left and right) to scan the string twice: once from left to right and then from right to left.

Steps:

1. Left-to-Right Pass:
   • Increment left for '(' and right for ')'.
   • When left equals right, update the maximum length.
   • If right becomes greater than left, reset both counters.
2. Right-to-Left Pass:
   • Do the reverse (increment counters accordingly).
   • When left equals right, update the maximum length.
   • If left exceeds right, reset both counters.

Note:
This approach is useful in cases where the valid sequence may be interrupted by more unmatched opening parentheses at the beginning.

Complexity:

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

Code Implementations

Python Implementation