A complete visual walkthrough of the stack-based approach — from brute force to an elegant O(n) solution.
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
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
Constraints:
0 <= s.length <= 3 * 104s[i] is '(', or ')'.The straightforward approach: try every possible substring, check if it is a valid parentheses string, and track the longest one.
For each start index i, try each end index j > i. Check if s[i..j] is valid by scanning with a counter (increment for '(', decrement for ')'; valid if counter never goes negative and ends at zero).
for (int i = 0; i < n; i++) { for (int j = i + 2; j <= n; j += 2) { if (isValid(s.substring(i, j))) maxLen = Math.max(maxLen, j - i); } }
for i := 0; i < n; i++ { for j := i + 2; j <= n; j += 2 { if isValid(s[i:j]) { if j-i > maxLen { maxLen = j - i } } } }
for i in range(n): for j in range(i + 2, n + 1, 2): if is_valid(s[i:j]): max_len = max(max_len, j - i)
for i in 0..n { let mut j = i + 2; while j <= n { if is_valid(&chars[i..j]) { max_len = max_len.max(j - i); } j += 2; } }
for (let i = 0; i < n; i++) { for (let j = i + 2; j <= n; j += 2) { if (isValid(s.slice(i, j))) maxLen = Math.max(maxLen, j - i); } }
This is O(n^3) — two nested loops to generate substrings times O(n) to validate each one. Far too slow for large inputs.
Key observation: The brute force re-validates overlapping substrings from scratch. We can do much better by processing the string left to right just once, using a stack to track unmatched positions.
Instead of storing parenthesis characters on the stack, we store their indices. This lets us compute the length of any valid substring by simple subtraction.
current index - stack.peek().Why does stack.peek() give us the length? The top of the stack is always the index of the last unmatched position — the boundary just before the current valid run. So i - stack.peek() gives the length of the contiguous valid substring ending at index i.
Let's trace the algorithm step by step on the input ")()())" (expected answer: 4).
| i | Char | Action | Stack | maxLen |
|---|---|---|---|---|
| — | — | Initialize | [-1] | 0 |
| 0 | ) | Pop -1; stack empty, push 0 as new base | [0] | 0 |
| 1 | ( | Push index 1 | [0, 1] | 0 |
| 2 | ) | Pop 1; length = 2 - 0 = 2 | [0] | 2 |
| 3 | ( | Push index 3 | [0, 3] | 2 |
| 4 | ) | Pop 3; length = 4 - 0 = 4 | [0] | 4 |
| 5 | ) | Pop 0; stack empty, push 5 as new base | [5] | 4 |
At index 4, the valid substring ()() spanning indices 1-4 has length 4. The final ')' at index 5 breaks the run and resets the base.
Notice the base marker role: Index 0 serves as the boundary after the initial ')' is unmatched. When we compute 4 - 0 = 4 at index 4, the base at 0 tells us the valid run started right after position 0.
class Solution { public int longestValidParentheses(String s) { int maxLen = 0; Deque<Integer> stack = new ArrayDeque<>(); // Push -1 as the base: "the index before any valid run" stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { // Open paren: push its index as potential start stack.push(i); } else { // Close paren: try to match stack.pop(); if (stack.isEmpty()) { // No match — this ')' becomes the new base stack.push(i); } else { // Valid match: length = current - new top maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; } }
func longestValidParentheses(s string) int { maxLen := 0 stack := []int{-1} // Push -1 as the base: "the index before any valid run" for i := 0; i < len(s); i++ { if s[i] == '(' { // Open paren: push its index as potential start stack = append(stack, i) } else { // Close paren: try to match stack = stack[:len(stack)-1] if len(stack) == 0 { // No match — this ')' becomes the new base stack = append(stack, i) } else { // Valid match: length = current - new top length := i - stack[len(stack)-1] if length > maxLen { maxLen = length } } } } return maxLen }
def longest_valid_parentheses(s: str) -> int: max_len = 0 stack: list[int] = [] # Push -1 as the base: "the index before any valid run" stack.append(-1) for i in range(len(s)): if s[i] == '(': # Open paren: push its index as potential start stack.append(i) else: # Close paren: try to match stack.pop() if not stack: # No match — this ')' becomes the new base stack.append(i) else: # Valid match: length = current - new top max_len = max(max_len, i - stack[-1]) return max_len
impl Solution { pub fn longest_valid_parentheses(s: String) -> i32 { let mut max_len = 0i32; let mut stack: Vec<i32> = vec![-1]; // base: "the index before any valid run" for (i, ch) in s.chars().enumerate() { if ch == '(' { // Open paren: push its index as potential start stack.push(i as i32); } else { // Close paren: try to match stack.pop(); if stack.is_empty() { // No match — this ')' becomes the new base stack.push(i as i32); } else { // Valid match: length = current - new top let length = i as i32 - stack.last().unwrap(); max_len = max_len.max(length); } } } max_len } }
function longestValidParentheses(s: string): number { let maxLen = 0; const stack: number[] = []; // Push -1 as the base: "the index before any valid run" stack.push(-1); for (let i = 0; i < s.length; i++) { if (s[i] === '(') { // Open paren: push its index as potential start stack.push(i); } else { // Close paren: try to match stack.pop(); if (stack.length === 0) { // No match — this ')' becomes the new base stack.push(i); } else { // Valid match: length = current - new top maxLen = Math.max(maxLen, i - stack[stack.length - 1]); } } } return maxLen; }
Enter a parentheses string and step through the algorithm. Watch the stack and character highlights update at each step.
We scan the string once from left to right. Each character triggers at most one push and one pop, so the total work is O(n). The stack can hold at most n indices in the worst case (e.g., all open parens), giving O(n) space. The DP approach also runs in O(n) time and O(n) space.
Two nested loops generate all O(n2) substrings. For each substring, a linear scan validates parentheses by tracking a counter -- O(n) per check. The three nested levels give O(n3). Only a running counter variable is needed.
A single left-to-right pass fills dp[i] with the length of the longest valid substring ending at index i. Each ')' looks back at most one dp entry to extend a previous valid run. One pass over n characters with O(1) work each gives O(n). The dp array stores n integers.
One pass through n characters; each character triggers at most one push and one pop -- amortized O(1) per character, O(n) total. The stack stores indices of unmatched parentheses and can grow up to n entries in the worst case (e.g., all open parens).
The stack stores indices (not characters) -- this lets us compute substring lengths on the fly. The top of the stack always marks the boundary just before the current valid run, so i - stack.peek() gives the length instantly. A two-pass counter approach can achieve O(1) space, but the stack solution is the standard interview choice.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.