Longest Valid Parentheses

Problem Description

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

Key Insights

• A valid parentheses substring is one where every opening parenthesis has a corresponding closing parenthesis.
• We can use a stack to track the indices of unmatched parentheses.
• Alternatively, dynamic programming can be employed to keep track of lengths of valid substrings ending at each index.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (for the stack or DP array)

Solution

To solve this problem, we can use a stack-based approach or a dynamic programming approach.

1. Stack Approach:

   • Traverse the string and use a stack to store the indices of the characters.
   • When encountering '(', push the index onto the stack.
   • When encountering ')', check if there is a corresponding '(' on the stack.
   • If matched, calculate the length of the valid substring.

2. Dynamic Programming Approach:

   • Use a DP array where dp[i] represents the length of the longest valid substring ending at index i.
   • Update the DP array based on the previous valid lengths and the current character.

Both approaches effectively track the balance of parentheses and determine the longest valid substring.

Code Solutions