Longest Valid Parentheses Solution for Microsoft
Company: Microsoft · Difficulty: Easy · Topics: String, Dynamic Programming, Stack
Problem Statement
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Examples
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output: 0
Explanation: Empty string has no valid parentheses.
Example 4:
Input: s = "((()))"
Output: 6
Explanation: The entire string is a valid parentheses substring.
Example 5:
Input: s = "()(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Intuition
The key insight is that valid parentheses must be balanced. We can use a stack to keep track of indices of opening parentheses and calculate the length of valid substrings. The crucial observation is that when we encounter a closing parenthesis, we need to find its matching opening parenthesis and calculate the length of the valid substring ending at the current position.
Approach
Approach 1: Stack (Optimal)
1. Use a stack to store indices of opening parentheses
2. Initialize stack with -1 to handle edge cases (this helps calculate length correctly)
3. For each character:
- If '(': push current index to stack
- If ')': pop from stack, calculate length if stack is not empty
4. Keep track of maximum length found
Approach 2: Dynamic Programming
1. Create a DP array where dp[i] represents length of valid parentheses ending at i
2. For each ')', check if there's a matching '(' before it
3. Update DP values and track maximum
Approach 3: Two Pass (Space Optimized)
1. Count '(' and ')' in both directions
2. Reset counters when they become unbalanced
3. Track maximum length in both passes
Dry Run
Let's trace through Example 2: s = ")()())"
Stack Approach:
- i=0, char=')': pop(), stack=[-1], maxLen=0
- i=1, char='(': push(1), stack=[-1,1]
- i=2, char=')': pop(), stack=[-1], len=2-(-1)=3, maxLen=3
- i=3, char='(': push(3), stack=[-1,3]
- i=4, char=')': pop(), stack=[-1], len=4-(-1)=5, maxLen=5
- i=5, char=')': pop(), stack=[-1], maxLen=5
DP Approach:
- dp[0] = 0, dp[1] = 0, dp[2] = 2, dp[3] = 0, dp[4] = 4, dp[5] = 0
- maxLen = 4 (from dp[4])
Solution
Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.
Key Insights:
1. Stack Approach: The key insight is using -1 as the initial stack value to handle edge cases properly
2. DP Approach: We can build the solution incrementally by considering valid parentheses ending at each position
3. Two Pass: We can optimize space by counting in both directions and resetting when unbalanced
Edge Cases:
- Empty string: return 0
- Single character: return 0
- All opening parentheses: return 0
- All closing parentheses: return 0
Time Complexity
- Best Case: O(n) - Single pass through the string
- Average Case: O(n) - Stack operations are O(1) amortized
- Worst Case: O(n) - When all characters are '('
Space Complexity
- Best Case: O(1) - Two pass approach
- Average Case: O(n) - Stack approach
- Worst Case: O(n) - When all characters are '('