Blind Plus 100 Visualized

#83 · Stack

Longest Valid Parentheses

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

HardLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Stack of unmatched indices

Push the index of every ( and, on ), pop. If the stack is empty afterwards the ) is unmatched and becomes the new base marker; otherwise the valid run ends at i and starts just after the new top. The stack bottom is always the position just before the current run.

Memory layout

A contiguous stack of indices, with −1 as an initial base so a run starting at 0 has a boundary.

OperationCost
per characterO(1)
spaceO(n)

Balance counters

Count ( and ) over a left-to-right sweep. Equal counts mean a balanced run; more ) than ( means the prefix is broken and the counters restart. A mirrored right-to-left sweep handles excess ( the first sweep cannot discard.

Memory layout

Two integers.

OperationCost
timeO(n) over two sweeps
spaceO(1)

Why it fits

  • Valid parentheses is a nesting property: a stack matches each ) with its latest unmatched (.
  • Storing indices, not characters, turns "matched" into a length: the run ends at i and starts after the nearest unmatched position.
  • The counter method uses the observation that a prefix with more ) than ( can never be part of a valid run, and symmetrically for suffixes.

Why alternatives degrade

A single balance counter in one sweep:
It misses runs after excess ( such as "(()": the counters never become equal. A reverse sweep is needed.
Recursion on matching pairs:
Correct but deep recursion on nested input and O(n²) in naive form.
Sorting or hashing the characters:
The problem depends on order and nesting, which these structures discard.

Four approaches, from naive to production

1 · beginner

Test every even-length substring

time O(n³)space O(1)

For each start and each end that gives an even length, scan the substring with a balance counter and check that it never goes negative and ends at zero.

bool isValid(const string& s, int from, int to) {
    int balance = 0;
    for (int k = from; k <= to; k++) {
        balance += s[k] == '(' ? 1 : -1;
        if (balance < 0) return false;
    }
    return balance == 0;
}
int longestValidParentheses(string s) {
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i + 1; j < (int)s.size(); j += 2) {
            if (isValid(s, i, j) && j - i + 1 > best) best = j - i + 1;
        }
    }
    return best;
}

Flaws & bottlenecks

  • About n²/4 substrings, each scanned in O(n).
  • Re-scans overlapping substrings from scratch.
  • Hopeless beyond a few hundred characters.

Interviewer cross-questions

Why only even lengths?

Say: Each ( needs exactly one ), so a valid string has equal numbers of both: its length is even.

What makes a string valid?

Say: The running balance never goes below 0 and ends at 0.

How can you avoid re-checking?

Say: Extend one scan per start while keeping the balance, or use a stack of indices.

2 · intermediate

Extend from every start with a running balance

time O(n²)space O(1)

For each start, scan right keeping a balance. Stop at the first negative balance; whenever the balance is 0 record the length.

int longestValidParentheses(string s) {
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        int balance = 0;
        for (int j = i; j < (int)s.size(); j++) {
            balance += s[j] == '(' ? 1 : -1;
            if (balance < 0) break;
            if (balance == 0) best = max(best, j - i + 1);
        }
    }
    return best;
}

Flaws & bottlenecks

  • Still quadratic: 10⁵ characters means 10¹⁰ steps in the worst case ("((((…" rescans a lot).
  • Restarts at every index even though a failure at j tells us about earlier starts.
  • Does not reuse work between starts.

Interviewer cross-questions

Why break when the balance goes negative?

Say: An unmatched ) can never be fixed by later characters, so no longer substring from this start is valid.

Why does a balance of 0 mean valid?

Say: It never went negative (else we would have stopped) and the counts are equal.

How do you reach O(n)?

Say: A stack of indices: each character is handled once, and run lengths come from index differences.

3 · advanced

Stack of indices with a base marker

time O(n)space O(n)

Keep a stack of indices starting with −1. Push each (. On ), pop; if the stack becomes empty push the index as a new base, otherwise the current run length is i − top.

int longestValidParentheses(string s) {
    vector<int> stack{-1};
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            stack.push_back(i);
        } else {
            stack.pop_back();
            if (stack.empty()) {
                stack.push_back(i);
            } else {
                best = max(best, i - stack.back());
            }
        }
    }
    return best;
}

Flaws & bottlenecks

  • O(n) stack space (a long run of "((((" fills it).
  • The base marker idea is easy to misremember.
  • Pushing the base back after a failed match needs care.

Interviewer cross-questions

Why start with −1?

Say: It acts as the boundary before index 0, so a valid run that starts at 0 has length i − (−1) = i + 1.

What does the stack top mean after a pop?

Say: The index just before the current valid run: either a still-unmatched ( or the base marker.

Can the stack be replaced by a DP array?

Say: Yes: dp[i] = length of the longest valid substring ending at i, in O(n) time and space; the stack is more direct.

4 · expert

Two counter sweeps (O(1) space)

time O(n)space O(1)

Sweep left to right with open and close counters: equal counts record 2 × close, and close > open resets. Then sweep right to left with the mirrored rule (open > close resets).

int longestValidParentheses(string s) {
    int best = 0;
    int open = 0, close = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') open++; else close++;
        if (open == close) best = max(best, 2 * close);
        else if (close > open) open = close = 0;
    }
    open = close = 0;
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        if (s[i] == '(') open++; else close++;
        if (open == close) best = max(best, 2 * open);
        else if (open > close) open = close = 0;
    }
    return best;
}

Flaws & bottlenecks

  • Why two sweeps are enough needs a proof to be convincing.
  • Two passes over the string.
  • Gives only the length, not the position (the stack version can also return it).

Interviewer cross-questions

Why does the left-to-right sweep alone fail?

Say: For "(()" the counters end at open = 2, close = 1 and never equal at the right moment; the valid "()" is only found when scanning from the right.

Why is resetting safe?

Say: In the forward sweep, close > open means the current prefix has an unmatched ), which no valid run can contain; the mirror argument holds for the backward sweep.

When would you choose this?

Say: When memory is tight or the string is huge: it needs constant extra space and two simple loops.

Synchronized code walkthrough

Showing: Test every even-length substring — shares the player above; click any step to jump.

bool isValid(const string& s, int from, int to) {
    int balance = 0;
    for (int k = from; k <= to; k++) {
        balance += s[k] == '(' ? 1 : -1;
        if (balance < 0) return false;
    }
    return balance == 0;
}
int longestValidParentheses(string s) {
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i + 1; j < (int)s.size(); j += 2) {
            if (isValid(s, i, j) && j - i + 1 > best) best = j - i + 1;
        }
    }
    return best;
}