Longest Valid Parentheses
Measure the longest stretch of a bracket string in which every parenthesis is matched.
Problem Understanding
The input string contains only ( and ). Return the length of the longest contiguous stretch in which every bracket is correctly matched and nested.
Example:
- Input:
(()-> Output:2(substring()). - Input:
)()())-> Output:4(substring()()).
Algorithm Strategy
We can use a Stack to store indices. The stack will help us calculate the length of valid substrings by tracking the 'base' index from which validity starts.
- Initialize stack with
-1. This acts as a base index for a valid substring starting at 0. - Iterate through string at index
i: - If
(:push(i). - If
):pop().- If stack is empty:
push(i). The current)is invalid and becomes the new base. - If stack not empty:
maxLen = max(maxLen, i - stack.top()). The valid substring is fromstack.top() + 1toi.
- If stack is empty:
Interactive Visualization
Visualize how storing indices helps calculate length. -1 is our initial base.
Dry Run
Input: )()())
| Idx | Char | Action | Stack | MaxLen |
|---|---|---|---|---|
| - | - | Init | [-1] |
0 |
| 0 | ) |
Pop -1. Stack empty. Push 0. | [0] |
0 |
| 1 | ( |
Push 1. | [0, 1] |
0 |
| 2 | ) |
Pop 1. Len = 2-0 = 2. | [0] |
2 |
| 3 | ( |
Push 3. | [0, 3] |
2 |
| 4 | ) |
Pop 3. Len = 4-0 = 4. | [0] |
4 |
| 5 | ) |
Pop 0. Stack empty. Push 5. | [5] |
4 |
Edge Cases & Common Mistakes
- Empty String: Length 0.
- All Open:
((((-> Length 0. - Initial Close:
)-> Resets base. - Base -1: Crucial for substrings starting at index 0.
Solution
Stack Logic O(N) Time O(N) Space.
Longest Valid Parentheses Code
1var longestValidParentheses = function(s) {2 const stack = [-1];3 let maxLen = 0;4 for (let i = 0; i < s.length; i++) {5 if (s[i] === '(') {6 stack.push(i);7 } else {8 stack.pop();9 if (stack.length === 0) {10 stack.push(i);11 } else {12 maxLen = Math.max(maxLen, i - stack[stack.length - 1]);13 }14 }15 }16 return maxLen;17};