Longest Valid Parentheses [Hard] — Stack, DP, and Two-Pass Counters

Problem Statement#

Given a string s containing only ( and ), return the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input:  s = "(()"
Output: 2
Explanation: The longest valid substring is "()", with length 2.

Example 2:

Input:  s = ")()())"
Output: 4
Explanation: The longest valid substring is "()()", with length 4.

Example 3:

Input:  s = ""
Output: 0

Constraints:

• 0 <= s.length <= 3 * 10^4
• s[i] is either '(' or ')'

Why This Problem Matters#

Longest Valid Parentheses is a canonical Hard problem that sits at the intersection of three different algorithmic ideas — stack-based index tracking, dynamic programming with carry-forward state, and a counting sweep that requires almost no extra space. Google and Amazon use it specifically because no single interview pattern solves it. A candidate who has only memorized "use a stack for parentheses" will reach a dead end when asked to reduce space to O(1). One who knows only the two-pass counter will struggle to explain why it works. The problem is a stress test for depth.

It also appears as a direct building block in more complex problems: validating nested structures, parsing expressions, and finding longest balanced substrings in compiler design and linter tooling. At Facebook/Meta, variants of this problem appear in the context of template-string validation. At Amazon, it shows up in bracket-matching for configuration DSLs. Understanding it at the level of all three approaches — and knowing when to use each — is the mark of an engineer who thinks beyond syntax.

Beyond the direct applications, this problem teaches a subtle but powerful insight: when you need to find the longest contiguous valid window, an index-sentinel stack is often more powerful than a character-matching stack, because it lets you compute lengths by subtraction rather than by counting matched pairs. That technique transfers directly to problems involving histogram areas, nested intervals, and expression parsing.

Three Approaches#

Approach 1 — Index-Sentinel Stack#

The core idea: Instead of using a stack to match parentheses, use it to track unmatched indices. Seed the stack with -1 as a sentinel base. Whenever you encounter an unmatched ), it becomes the new base. The length of the current valid window is always i - stack[-1].

Why the sentinel works: At any point, stack[-1] holds the index of the last character that could not be included in any valid substring. The gap between the current index and this sentinel is exactly the length of the valid substring ending here.

Walk through it mentally:

• Push index of every ( onto the stack.
• For every ), pop from the stack.
  • If the stack is now empty, the ) is unmatched — push its index as the new base.
  • If the stack is not empty, i - stack[-1] gives the length of the valid run ending at i.

This is O(n) time and O(n) space in the worst case (all open brackets).

Approach 2 — Dynamic Programming#

The core idea: Define dp[i] as the length of the longest valid substring ending at index i. Every valid substring must end with ), so dp[i] is 0 whenever s[i] == '('.

The recurrence: When s[i] == ')':

1. Case A — s[i-1] == '(': The two characters form (). The valid run ending at i is dp[i-2] + 2 (extend whatever valid run ended just before this pair).

2. Case B — s[i-1] == ')': The character before us closes its own valid run of length dp[i-1]. We need to check whether the character just before that run is a matching (. That character sits at index j = i - dp[i-1] - 1. If s[j] == '(', then dp[i] = dp[i-1] + 2 + dp[j-1] (the run before j may also be valid and can be appended).

The answer is the maximum value in the dp array.

This is O(n) time and O(n) space.

Approach 3 — Two-Pass Counters (O(1) Space)#

The core idea: Scan left-to-right keeping counters left and right for the number of ( and ) seen so far.

• When left == right, we have a valid window of length left + right — update the answer.
• When right > left, we have an excess of ) — reset both counters to 0.

The catch: this left-to-right pass never detects valid windows anchored on the left by excess (. Example: "(()" — left will always exceed right, so we never update the answer. Fix this by doing a second pass right-to-left with the reset condition flipped: reset when left > right.

Why two passes are sufficient: Any valid substring is either "balanced from the start" (caught by the left-to-right pass) or "balanced from the end" (caught by the right-to-left pass). Together they cover all cases with O(1) extra space.

Visual Dry Run#

Let's trace all three approaches on the same string: s = ")()())".

Expected output: 4 (the substring "()()" from index 1 to 4).

Stack Trace#

Stack starts: [-1]   (sentinel)
ans = 0
 
i=0, s[0]=')'
  Pop -1. Stack is now empty → push 0 as new base.
  Stack: [0]
 
i=1, s[1]='('
  Push index 1.
  Stack: [0, 1]
 
i=2, s[2]=')'
  Pop 1. Stack not empty. ans = max(0, 2 - 0) = 2.
  Stack: [0]
 
i=3, s[3]='('
  Push index 3.
  Stack: [0, 3]
 
i=4, s[4]=')'
  Pop 3. Stack not empty. ans = max(2, 4 - 0) = 4.
  Stack: [0]
 
i=5, s[5]=')'
  Pop 0. Stack is now empty → push 5 as new base.
  Stack: [5]
 
Final ans = 4  ✓

Notice how the sentinel at index 0 (the position of the first unmatched )) acts as the base. When we reach index 4, 4 - 0 = 4 gives us the full length of "()()" in one subtraction.

DP Trace#

s = ) ( ) ( ) )
i:  0 1 2 3 4 5
 
dp = [0, 0, 0, 0, 0, 0]   (all zeros initially)
ans = 0
 
i=0, s[0]=')': s[i-1] is out of range. dp[0] = 0.
 
i=1, s[1]='(': dp[1] = 0  (open bracket always 0)
 
i=2, s[2]=')':
  s[i-1] = s[1] = '(' → Case A: dp[2] = dp[0] + 2 = 0 + 2 = 2
  ans = max(0, 2) = 2
 
i=3, s[3]='(': dp[3] = 0
 
i=4, s[4]=')':
  s[i-1] = s[3] = '(' → Case A: dp[4] = dp[2] + 2 = 2 + 2 = 4
  ans = max(2, 4) = 4
 
i=5, s[5]=')':
  s[i-1] = s[4] = ')' → Case B:
    j = i - dp[i-1] - 1 = 5 - 4 - 1 = 0
    s[0] = ')' ≠ '(' → no match. dp[5] = 0.
 
Final dp = [0, 0, 2, 0, 4, 0]
ans = 4  ✓

The DP table shows clearly how dp[4] = 4 absorbs both () pairs — it carries the length of the valid run ending at index 2 forward through dp[2].

Two-Pass Counter Trace#

Left-to-right:

left=0, right=0, ans=0
 
i=0 ')': right=1.  right > left → reset left=0, right=0
i=1 '(': left=1.
i=2 ')': right=1.  left==right → ans = max(0, 2) = 2
i=3 '(': left=2.
i=4 ')': right=2.  left==right → ans = max(2, 4) = 4
i=5 ')': right=3.  right > left → reset left=0, right=0
 
ans after L→R pass = 4

Right-to-left:

left=0, right=0, ans=4   (carry forward from first pass)
 
i=5 ')': right=1.
i=4 ')': right=2.
i=3 '(': left=1.  (left < right, no reset)
i=2 ')': right=3.
i=1 '(': left=2.
i=0 ')': right=4.
 
Note: left never exceeds right in this example, so no reset triggered.
ans remains 4.

In this example the left-to-right pass found the answer. The right-to-left pass is essential for inputs like "(()" where left always exceeds right going forward.

Counter trace for "(()":

Left-to-right:

i=0 '(': left=1
i=1 '(': left=2
i=2 ')': right=1  — left != right, right < left, no action
Answer from L→R = 0  (missed!)

Right-to-left:

i=2 ')': right=1
i=1 '(': left=1.  left==right → ans = max(0, 2) = 2
i=0 '(': left=2.  left > right → reset
Answer = 2  ✓

Common Mistakes#

Mistake 1 — Initializing the stack empty instead of with -1.

The most common bug. If you start with an empty stack, when you pop on a matching ) and the stack becomes empty, you have no reference point to compute the window length. You cannot do i - stack[-1] because the stack is empty. Candidates patch this with a special case that often misses edge cases. The sentinel -1 means "nothing valid was here before index 0," which is exactly the right base for every computation.

Mistake 2 — Using the stack to count matched pairs instead of tracking indices.

A natural instinct is to push ( and pop on ), counting how many pops succeed. This tells you how many pairs exist, but not whether they are contiguous. For "()(()", a pair-counting stack gives 2 pairs = length 4, but the answer is 2 ("()" at positions 0-1, and another "()" at 3-4, neither contiguous with length 4). The index-sentinel approach gives the right answer because it computes gap lengths, not pair counts.

Mistake 3 — Off-by-one in the DP recurrence for Case B.

When s[i] == ')' and s[i-1] == ')', the matching ( sits at j = i - dp[i-1] - 1. Candidates frequently write j = i - dp[i-1] (off by one) or forget to check that j >= 0 before accessing s[j]. Both errors produce wrong answers or index-out-of-bounds exceptions on strings like "())" or "()". Always bounds-check j >= 0 before the array access.

Mistake 4 — Forgetting dp[j-1] in Case B.

In Case B, once you confirm s[j] == '(', the full contribution is dp[i-1] + 2 + dp[j-1]. The dp[j-1] term accounts for any valid substring that immediately precedes position j. Candidates who omit it will get wrong answers on inputs like "()()" when processed as two consecutive ) characters completing a longer chain.

Mistake 5 — Two-pass approach missing the right-to-left pass.

It is tempting to believe the left-to-right pass is sufficient. It is not. Try it on "(()" — you never update ans because left always stays ahead of right and never triggers a reset. The right-to-left pass is not an optimization; it is a correctness requirement for any string that begins with unmatched (.

Mistake 6 — Returning left + right instead of the running max.

In the two-pass counter, the answer should be updated every time left == right, not just at the end. The maximum valid window might appear in the middle of the string. If you only look at left + right after the full pass, you miss internal windows.

Solutions#

Approach 1 — Stack with Index Sentinel#

Python

def longestValidParentheses(s: str) -> int:
    # Sentinel value: represents the "wall" before the string starts.
    # This lets us compute window lengths by subtraction without special cases.
    stack = [-1]
 
    ans = 0
 
    for i, ch in enumerate(s):
        if ch == '(':
            # Push the index of every open bracket.
            # We will use this index later when we find its matching ')'.
            stack.append(i)
        else:
            # ')' encountered: pop the top (either a matching '(' or the base)
            stack.pop()
 
            if not stack:
                # Stack is empty: this ')' is unmatched.
                # Push its index as the new base (sentinel).
                stack.append(i)
            else:
                # Stack still has elements: stack[-1] is the last unmatched index.
                # The window from stack[-1]+1 to i is entirely valid.
                ans = max(ans, i - stack[-1])
 
    return ans

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
function longestValidParentheses(s) {
    // Seed the stack with -1 as the base sentinel.
    // This represents a "wall" at position -1 so that length = i - stack[top].
    const stack = [-1];
    let ans = 0;
 
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            // Record the index of every open bracket for later matching.
            stack.push(i);
        } else {
            // Pop: either consumes a matching '(' or the current base sentinel.
            stack.pop();
 
            if (stack.length === 0) {
                // Unmatched ')' — install it as the new base sentinel.
                stack.push(i);
            } else {
                // Valid window from stack[top]+1 to i; length = i - stack[top].
                ans = Math.max(ans, i - stack[stack.length - 1]);
            }
        }
    }
 
    return ans;
}

Approach 2 — Dynamic Programming#

Python

def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
 
    # dp[i] = length of the longest valid substring ENDING at index i.
    # A valid substring must end with ')', so dp[i] = 0 whenever s[i] == '('.
    dp = [0] * n
    ans = 0
 
    for i in range(1, n):
        if s[i] == ')':
            if s[i - 1] == '(':
                # Case A: s[i-1..i] is "()" — a direct pair.
                # Extend whatever valid run existed just before this pair.
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
 
            elif dp[i - 1] > 0:
                # Case B: s[i-1] is ')' and it closes its own valid run.
                # The character immediately before that run is at index j.
                j = i - dp[i - 1] - 1
 
                if j >= 0 and s[j] == '(':
                    # s[j] matches s[i]. Add 2 for this pair, dp[i-1] for the
                    # inner run, and dp[j-1] for any valid run before s[j].
                    dp[i] = dp[i - 1] + 2 + (dp[j - 1] if j >= 1 else 0)
 
            ans = max(ans, dp[i])
 
    return ans

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
function longestValidParentheses(s) {
    const n = s.length;
    if (n === 0) return 0;
 
    // dp[i] = length of the longest valid substring ending exactly at index i.
    // Initialized to 0; we only update when s[i] === ')'.
    const dp = new Array(n).fill(0);
    let ans = 0;
 
    for (let i = 1; i < n; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                // Case A: direct "()" pair at positions i-1 and i.
                // Append 2 to whatever valid run ended at i-2.
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
 
            } else if (dp[i - 1] > 0) {
                // Case B: s[i-1] is ')' ending a run of length dp[i-1].
                // The potential matching '(' sits just before that run.
                const j = i - dp[i - 1] - 1;
 
                if (j >= 0 && s[j] === '(') {
                    // Combine: inner run + this new pair + run before j.
                    dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
                }
            }
 
            ans = Math.max(ans, dp[i]);
        }
    }
 
    return ans;
}

Approach 3 — Two-Pass Counters (O(1) Space)#

Python

def longestValidParentheses(s: str) -> int:
    ans = 0
 
    # --- Left-to-right pass ---
    # Counts open and close brackets seen so far.
    # Resets when right exceeds left (excess unmatched ')').
    left = right = 0
    for ch in s:
        if ch == '(':
            left += 1
        else:
            right += 1
 
        if left == right:
            # Perfectly balanced window found — record its total length.
            ans = max(ans, left + right)
        elif right > left:
            # Excess ')' breaks any valid window. Start fresh.
            left = right = 0
 
    # --- Right-to-left pass ---
    # Catches valid windows that are "anchored" by excess '(' on the left,
    # which the L→R pass misses because right never catches up to left.
    left = right = 0
    for ch in reversed(s):
        if ch == '(':
            left += 1
        else:
            right += 1
 
        if left == right:
            ans = max(ans, left + right)
        elif left > right:
            # Excess '(' (reading right-to-left) breaks the window. Reset.
            left = right = 0
 
    return ans

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
function longestValidParentheses(s) {
    let ans = 0;
 
    // --- Left-to-right pass ---
    // Track counts of '(' and ')'. Reset on excess ')'.
    let left = 0, right = 0;
    for (const ch of s) {
        if (ch === '(') {
            left++;
        } else {
            right++;
        }
 
        if (left === right) {
            // Found a balanced window of total length left+right.
            ans = Math.max(ans, left + right);
        } else if (right > left) {
            // Unmatched ')' — nothing before this can be part of a valid window.
            left = right = 0;
        }
    }
 
    // --- Right-to-left pass ---
    // Catches valid windows blocked by leading unmatched '('.
    left = right = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === '(') {
            left++;
        } else {
            right++;
        }
 
        if (left === right) {
            ans = Math.max(ans, left + right);
        } else if (left > right) {
            // Unmatched '(' going right-to-left — reset.
            left = right = 0;
        }
    }
 
    return ans;
}

Complexity Analysis#

When to choose which:

• Interview default: Start with the stack. It is the most intuitive to explain and the easiest to trace on a whiteboard. The sentinel trick is elegant and concise.
• Follow-up challenge: If the interviewer asks for O(1) space, pivot to the two-pass counter. It requires no stack, no array — just four integers.
• DP when asked: The DP solution is worth knowing because it generalizes well to problems that require you to combine sub-results (e.g., counting, not just maximizing). It is also a useful bridge to understanding interval DP.

Note that all three solutions have the same O(n) time complexity — the constant factor difference between one pass and two passes is negligible at interview scale.

Follow-up Questions#

These are real follow-ups asked at Google, Amazon, and Meta after the base problem is solved.

Q1: Can you solve it in O(1) space?

Yes — the two-pass counter approach. Explain the two-pass logic and why a single pass is insufficient. The key insight: a left-to-right pass handles strings with trailing (, but not leading (. The right-to-left pass covers the mirror case.

Q2: What if you need to return the actual substring, not just the length?

Track the starting index of the best window alongside the length. In the stack approach, when you compute length = i - stack[-1], the window starts at stack[-1] + 1. Keep best_start and best_len. Return s[best_start : best_start + best_len].

Q3: What if the input contains characters other than ( and )?

Treat any non-bracket character as an unmatched element that breaks any valid window. In the stack approach, push its index as a new base sentinel (same as an unmatched )). In the two-pass approach, reset both counters on encountering an unknown character. This variant appears in linter and expression-parser problems.

Q4: What if you have multiple types of brackets — (), [], {}?

The two-pass counter approach breaks down because (] would incorrectly appear balanced. The stack approach generalizes: push a tuple of (bracket_type, index) for open brackets, and on close brackets verify the popped element matches the expected type. If it does not match, treat the unmatched close bracket as a base sentinel.

Q5: Find all valid parentheses substrings, not just the longest.

Use the stack approach. Every time you update ans = i - stack[-1], the window [stack[-1]+1, i] is a maximal valid block at that point. You can collect all such windows. To enumerate all valid substrings (including nested and overlapping ones), use DP: dp[i] gives the length of the maximal valid substring ending at i, and substrings of length 2, 4, ... up to dp[i] are also valid at that position.

Q6: What is the minimum number of bracket removals to make a string valid?

A related but distinct problem (LeetCode 921). Use a single pass: count unmatched ( and unmatched ) simultaneously. Unmatched ) is detected immediately (counter goes negative); unmatched ( is the residual at the end. The answer is their sum. This is a direct cousin of the current problem and often asked in the same interview session.

This Pattern Solves#

The index-sentinel stack technique from Approach 1, and the DP carry-forward from Approach 2, appear in these problems:

• LeetCode 84 — Largest Rectangle in Histogram: index-sentinel stack for tracking span widths
• LeetCode 85 — Maximal Rectangle: extends LC 84 row by row
• LeetCode 20 — Valid Parentheses: simpler cousin — the stack approach without length tracking
• LeetCode 921 — Minimum Add to Make Parentheses Valid: counter-based, same balance idea
• LeetCode 1249 — Minimum Remove to Make Valid Parentheses: stack of unmatched indices, then remove them
• LeetCode 678 — Valid Parenthesis String: DP or greedy range tracking for wildcard *

Key Takeaways#

• Stack approach: initialize the stack with sentinel -1; push index on (; pop on ) and compute length as i - stack[-1]; push i if stack is empty after pop. O(n) time, O(n) space.
• The sentinel -1 eliminates a special case: it provides a left boundary for valid substrings that start at index 0, so the length formula i - stack[-1] always works.
• DP approach: dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2] when s[i] == ')' and its matching ( exists. Combines the inner valid block plus any valid block immediately before the opening (.
• Two-pass counter (O(1) space): count left/right parens left-to-right (reset on right excess) and right-to-left (reset on left excess); take the max window from both passes.
• The two-pass approach works because any valid substring is captured in exactly one pass — if it was missed left-to-right (extra leading (), it is captured right-to-left.
• Edge case: empty string and all-same-character strings should return 0, not crash.
• This problem is frequently followed up with LC 921 (Minimum Add to Make Valid) and LC 1249 (Minimum Remove to Make Valid) — all three share the balance/deficit counting idea.