The trick isn't storing brackets. It's storing indices — because the answer is a length, and lengths are measured between boundaries.
Given a string of only ( and ), find the length of the longest
contiguous substring that forms valid parentheses. For ()(()(()), the longest
valid run is ()(()) — length 6.
Checking whether a whole string is balanced is easy: a counter or a stack will do. This is harder. A valid region can be buried inside an invalid string, so you also have to figure out where each valid region starts, where it ends, and how wide it is.
( as +1 and ) as −1. A string is valid only if the running balance never
goes negative and ends at exactly 0. )( ends at 0 but dips to −1 first,
so it's invalid.
The obvious idea — generate all substrings, validate each, keep the longest — is roughly O(n³): about n²
substrings, each costing up to O(n) to check. With n up to 100,000, even O(n²) is far too slow. We
need something close to O(n), which means each character can only be looked at a constant
number of times.
An ( can't be resolved until a future ) arrives — the classic signal to reach for a
stack. But a stack of characters only tells you that something matched, not how far apart the
match was. Since the answer is a length, you need positions.
Take )()(). The valid part is ()(), from index 1 to 4 — length 4. That leading
) at index 0 is a wall; nothing valid can reach across it. So the thing you actually need to
remember is the index just before the current valid region begins.
When you match a ), the valid substring runs from right after that boundary up to the current
position. That gives the whole formula:
i − stack.peek()
To measure the gap between two fence posts you record the posts' positions, not the planks between them. The unmatched brackets are the posts; the valid run is the gap you measure.
Each unmatched bracket is a pothole splitting the road into stretches. You want the longest smooth stretch — so you track where the potholes are, then measure between them.
A ruler measures from a fixed zero. The sentinel -1 is that zero mark placed just before the
string, so the first valid run measures cleanly with no special case.
At the very start there's no unmatched bracket to serve as a boundary. Instead of writing special-case code,
pretend a boundary lives at index -1 and seed the stack with it: stack = [-1]. Now
() matches, the stack returns to [-1], and the length is 1 − (−1) = 2
with zero fuss.
So the stack always holds: the indices of unmatched (, sitting on top of one boundary index at the
bottom (the sentinel, or the position of the last unmatched )).
stack = [-1] # sentinel boundary maxLen = 0 for i, ch in string: if ch == '(': push(i) # unmatched open, remember where else: # ch == ')' pop() # cancel the matching '(' if stack is empty: push(i) # unmatched ')' -> new boundary else: maxLen = max(maxLen, i - peek())
pop first, then read peek(). Before the pop the top is just the (
you're matching; only after the pop does the top become the boundary before the valid region.
Pick an example and walk it one character at a time. Teal cells are unmatched ( indices, the blue
cell is the -1 sentinel, and amber cells are unmatched ) boundaries. When a
) matches, the valid range lights up and the length is computed as i − top.
For ()(()(()) (indices 0–8), watch how the top of the stack is always the boundary the current
valid run can't cross:
| i | ch | Action | Stack | Length |
|---|---|---|---|---|
| 0 | ( | push 0 | [-1, 0] |
— |
| 1 | ) | pop 0 → len 1−(−1) | [-1] |
2 |
| 2 | ( | push 2 | [-1, 2] |
— |
| 3 | ( | push 3 | [-1, 2, 3] |
— |
| 4 | ) | pop 3 → len 4−2 | [-1, 2] |
2 |
| 5 | ( | push 5 | [-1, 2, 5] |
— |
| 6 | ( | push 6 | [-1, 2, 5, 6] |
— |
| 7 | ) | pop 6 → len 7−5 | [-1, 2, 5] |
2 |
| 8 | ) | pop 5 → len 8−2 | [-1, 2] |
6 |
At index 8 the top is 2 — index 2 is a still-unmatched (, so the valid run can't
cross it. The run therefore starts at index 3 and the length is 8 − 2 = 6, matching
()(()).
) splits them. The longest
contiguous run is only 2. Pair count ignores boundaries.() inside is valid. One number can't remember
where the unmatched bracket sat.Both shortcuts throw away position. The index stack keeps it, which is exactly why it wins.
ArrayDequeimport java.util.*; public class Main { static int longestValidParentheses(String s) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(-1); // sentinel boundary int maxLen = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); // remember unmatched '(' } else { stack.pop(); // cancel a matching '(' if (stack.isEmpty()) { stack.push(i); // unmatched ')' becomes boundary } else { maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; } }
Prefer Deque<Integer> backed by ArrayDeque over the legacy Stack
class — push, pop, and peek all behave as expected. Every index is pushed
and popped at most once, so it's O(n) time, O(n) space.
| Approach | Time | Space | Difficulty | Generality |
|---|---|---|---|---|
| Brute force | O(n³) | O(1) | Easy | Low |
| Index stack | O(n) | O(n) | Medium | High |
| Two-scan counters | O(n) | O(1) | Higher | Medium |
The two-scan trick keeps left/right counters and scans left-to-right, resetting when
right > left and recording 2·right when they're equal. That alone misses strings
with excess ( like (()(, so you scan again right-to-left with the mirror rule (reset
when left > right). Two passes, O(1) space.