Coding · Stacks
Longest Valid Parentheses
- Reported once
- Hard
- internship
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given a string made only of the characters ( and ), return the length of the longest contiguous substring that is a balanced run of parentheses, where every opening bracket is closed in the right order. For the string )()()) the answer is 4, from the substring ()(). The string can be 30,000 characters long, so checking every substring is too slow.
Restated in our own words, not a quote from Groww or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: does the string contain only parentheses, or other characters I should ignore? Do I need a contiguous substring, or a subsequence? Does valid mean every opener is matched, in the right order? What do I return for an empty string, or when nothing matches? How long can the string be?
I would assume only ( and ), a contiguous substring, the standard balancing rules, and 0 when no pair exists. I will return the length, not the substring itself.
Brute force
Say the obvious answer and why it is too slow.
Check every substring: for each start and each even length, scan it with a counter that goes up for an opener and down for a closer, rejecting it if the counter goes negative or does not end at zero. That is O(n²) substrings, each checked in O(n), so O(n³) in total. Stopping a start's scan as soon as the counter goes negative, and extending one character at a time, cuts it to O(n²).
With 30,000 characters, n² is nearly a billion steps, and n³ is hopeless. Both repeat work: the substring from i to j shares all but two of its characters with the one from i to j - 2, yet it is scanned again from scratch.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n³), or O(n²) with early exit
- Time
- O(n)
- Space
- O(n)
The pattern is a stack of indices. Keep a stack whose bottom is the index of the last position that cannot belong to the run being built, starting with -1 as a floor. Scan the string. On an opener, push its index. On a closer, pop the stack. If the stack is now empty, this closer has no partner, so push its index as the new floor. Otherwise the run ending here has length i minus the index now on top of the stack, so update the best length.
Why it is correct: the stack holds the indices of unmatched openers, and its bottom is the most recent unmatched closer (or -1). After popping the partner of the current closer, the top of the stack is the nearest position to the left that is not matched. Everything between that position and i is made of matched pairs, so i minus top is the longest valid run that ends at i. Taking the maximum over every i gives the longest overall, since the longest run has to end somewhere.
Each index is pushed and popped at most once, so time is O(n), and the stack can hold up to n indices, so space is O(n). There is also an O(1) space solution with one left-to-right and one right-to-left counter pass, and a DP; I would mention both as alternatives. I would say it as: the stack remembers where the current good stretch begins, and a closer that empties it starts a new stretch.
Walk it through
A dry run on the example, step by step.
| i | char | Action | Stack after | Best |
|---|---|---|---|---|
| start | - | floor at -1 | [-1] | 0 |
| 0 | ) | pop -1, empty, push 0 | [0] | 0 |
| 1 | ( | push 1 | [0,1] | 0 |
| 2 | ) | pop 1, 2 - 0 = 2 | [0] | 2 |
| 3 | ( | push 3 | [0,3] | 2 |
| 4 | ) | pop 3, 4 - 0 = 4 | [0] | 4 |
| 5 | ) | pop 0, empty, push 5 | [5] | 4 |
Use )()()) with the stack starting as [-1]. Index 0 is a closer: pop -1, the stack is empty, so push 0 as the new floor. Index 1 is an opener: push it, stack [0, 1]. Index 2 is a closer: pop 1, the top is 0, length 2 - 0 = 2, best 2. Index 3 is an opener: stack [0, 3]. Index 4 is a closer: pop 3, the top is 0, length 4 - 0 = 4, best 4. The length reaches back across the earlier matched pair to the floor, which is how neighboring valid runs merge.
Index 5 is a closer: pop 0, the stack is empty, so push 5 as the floor, and the best stays 4. The answer is 4. The trace shows the stack after each step.
The code
Runnable JavaScript, checked against test cases.
function longestValidParentheses(s) {
const stack = [-1];
let longest = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") {
stack.push(i);
continue;
}
stack.pop();
if (stack.length === 0) {
stack.push(i);
} else {
longest = Math.max(longest, i - stack[stack.length - 1]);
}
}
return longest;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty string: the loop never runs and the result is 0. Only openers, like (((: they pile up on the stack, no closer ever pops one, and the length is never updated, so 0. Only closers, like ))): each pop empties the stack and the closer becomes the floor, so 0 again. A single pair gives 2.
Neighboring runs, like ()(()): the floor stays at -1, so the whole string measures 6 in one piece. An unmatched opener in the middle, like the string ()(() with five characters, leaves the best at 2, because the opener at index 2 stays on the stack and blocks the merge. The -1 floor lets a run that starts at index 0 get its full length with no special case.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it in O(1) extra space with two counters and two passes?
- How would you write the dynamic programming version, and what is its recurrence?
- How would you return the substring itself, not just its length?
- What changes if the string also contains square and curly brackets?
- How would you count how many substrings reach the longest length?
Where candidates slip
The mistakes this problem punishes.
The usual slip is a missing -1 floor: without it, a valid run that starts at index 0 is measured as i instead of i + 1. A second is computing the length from the index you just popped, which measures only the innermost pair (and is off by one), not the merged run; use the index left on top after the pop. A third is forgetting to push the closer when the stack becomes empty, so later runs measure from the wrong floor.
Others: answering with the count of matched pairs times two, which counts pairs that are not adjacent (for the string ()(() it gives 4, but the answer is 2); using a stack of characters, which cannot report positions; and writing the DP with the wrong recurrence for two closers in a row.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.