FAANGPrep Sprint
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
")()())"
BASE -1
string
)
0
(
1
)
2
(
3
)
4
)
5
stack · indices
-1
TOP · base
Run
—
Best
0
Start the stack with -1: the base a valid run starting at index 0 measures from
Next
')' at 0: pop -1, the old base
String
Visualize how storing indices helps calculate length. -1 is our initial base.