Valid Parenthesis String

Introduction

The classic parenthesis problem is a two-line stack trick: push on (, pop on ), valid iff the stack is empty at the end. Add a single wildcard — a * that can be (, ), or empty — and that trick shatters. Every * branches the set of reachable states three ways; by the end of a long string you are staring at an exponential search tree.

What makes this chapter worth a slot is the move the problem demands. Instead of tracking the count of open parens, you track the range of counts still reachable. A ( shifts the range up. A ) shifts it down. A * widens it. The string is valid iff 0 sits inside the range after the last character — and iff the ceiling never fell below 0 along the way.

When every character offers three choices, don’t pick — track the band of outcomes all of them can still reach.

Read this chapter linearly if parenthesis problems feel scary; jump to the greedy approach and the band viz if you’ve seen the brute force before.

What the interviewer is actually testing

This problem is graded on four things, in roughly this order:

1. Recognition that the stack trick breaks. A candidate who reaches for std::stack on the first * and never revisits the decision has revealed a ceiling.
2. Willingness to start from the brute force. Name the exponential baseline first. Rushing to the greedy insight without acknowledging what you’re skipping reads as over-pattern-matched.
3. The DP instinct. Spot the overlapping subproblems. Even if you don’t write the code, say the words “I could memoize this over substring endpoints.”
4. The greedy leap. Arrive at min/max tracking without being prompted. This is the senior signal — few candidates reach it under time pressure.

Every section below is organized around hitting those four marks.

Problem statement

Clarifying questions — and why each one matters

The problem arrives slightly under-specified. What you ask in the first sixty seconds is scored directly.

A mental framework — why the stack dies

If the * weren’t in the alphabet, a single integer would solve this problem. Scan left to right. On (, increment; on ), decrement. Invalid if the counter ever goes negative, invalid at the end if the counter isn’t zero. That’s the standard stack trick in its leanest form (you don’t even need the stack; a counter suffices because there’s only one bracket type).

The * breaks that. After processing a prefix containing k stars, the “open-paren count so far” is not a single number — it is a set of 3^k possible numbers, one per way of resolving the stars you’ve seen. You cannot enumerate that.

But the set has a redeeming structure:

1. It’s contiguous. Between the smallest and largest reachable counts, every integer in between is also reachable. You can shift any *-as-( to *-as-) one step at a time, and each step changes the count by exactly 2. (Proof sketch: the count under any resolution is determined only by how many stars become (, how many become ), and how many become empty — three independent knobs that change the count linearly.)
2. It’s nonnegative at every step — you clamp below at 0, because a prefix that would require a negative count represents an unmatched ) in every resolution, which is already invalid.

So the “set of possible counts” collapses to two integers: the minimum low and the maximum high still reachable. That’s the algorithm.

Discussion

#include <string>

namespace {
bool solve(const std::string& s, std::size_t pos, int open, int closed) {
    if (closed > open) return false;
    if (pos == s.size()) return open == closed;

    const char c = s[pos];
    if (c == '(' || c == '*') {
        if (solve(s, pos + 1, open + 1, closed)) return true;
    }
    if (c == ')' || c == '*') {
        if (solve(s, pos + 1, open, closed + 1)) return true;
    }
    if (c == '*') {
        if (solve(s, pos + 1, open, closed)) return true;
    }
    return false;
}
}  // namespace

bool checkValidString(const std::string& s) {
    return solve(s, 0, 0, 0);
}

#include <cstdint>
#include <string>
#include <vector>

namespace {
enum class Cell : std::int8_t { Unknown, Yes, No };

bool solve(const std::string& s, int i, int j, std::vector<std::vector<Cell>>& dp) {
    if (i > j) return true;
    if (dp[i][j] != Cell::Unknown) return dp[i][j] == Cell::Yes;

    bool ok = false;
    const char c = s[i];

    if (c == '*') {
        ok = solve(s, i + 1, j, dp);
    }
    if (!ok && c != ')') {
        for (int k = i + 1; k <= j && !ok; ++k) {
            if (s[k] == ')' || s[k] == '*') {
                ok = solve(s, i + 1, k - 1, dp) && solve(s, k + 1, j, dp);
            }
        }
    }

    dp[i][j] = ok ? Cell::Yes : Cell::No;
    return ok;
}
}  // namespace

bool checkValidString(const std::string& s) {
    if (s.empty()) return true;
    const int n = static_cast<int>(s.size());
    std::vector<std::vector<Cell>> dp(n, std::vector<Cell>(n, Cell::Unknown));
    return solve(s, 0, n - 1, dp);
}

#include <algorithm>
#include <string>

bool checkValidString(const std::string& s) {
    int low = 0;
    int high = 0;
    for (const char c : s) {
        if (c == '(') {
            ++low;
            ++high;
        } else if (c == ')') {
            low = std::max(low - 1, 0);
            --high;
            if (high < 0) return false;
        } else {
            low = std::max(low - 1, 0);
            ++high;
        }
    }
    return low == 0;
}

Approach comparison

Default answer: the greedy band. State that out loud when you close.

Follow-ups to anticipate

Pattern recognition — tracking a band of possibilities

The move this chapter teaches generalizes. When each step of a scan offers a commutative family of local choices and you only need a yes/no answer at the end, you often don’t need to explore all interpretations — you need to track the range of outcomes they could produce.

Places the same pattern appears:

• Jump Game (LeetCode 55). Track the farthest reachable index rather than every reachable index. Same collapse.
• Regex Matching with ? and *. ? widens the match band by one character; * widens it by any number. DP tables are the standard formulation, but the insight is the same.
• Wildcard schedulers. When a job has a range of allowed start times, carry the range through dependencies rather than enumerating start times.
• Interval-bound propagation in SAT / constraint solvers. Each variable has a reachable range; constraints prune the range; clamp at implied bounds.
• Abstract interpretation in compilers. Integer-typed variables carry a range of reachable values through straight-line code; branches narrow the range, loops widen it. Same machinery, built to run at compile time.

The reflex you want: when a character (or step) has more than one valid interpretation, ask “can I represent the set of post-step states as a range rather than a list?” When yes, the exponential collapses.

What to say out loud — the delivery script

Ten beats. Rehearse until fluid.

1. “Let me repeat: I have a string over (, ), *, and I need to decide if some interpretation of the stars makes it balanced.”
2. Ask: “Boolean or reconstruction? Empty string valid? Any other characters?”
3. “Without * this is trivial — a counter that tracks open-paren balance. The * is what makes it hard because each one branches three ways.”
4. “Brute force is $O(3^n)$: try every interpretation. Too slow, but correct. I’ll name it and move on.”
5. “The subproblems overlap: every substring’s validity is a distinct question. I could memoize over $(i, j)$ endpoints for $O(n^3)$. I’d ship that if I needed to reconstruct the interpretation.”
6. “For the boolean question there’s something better. Instead of tracking the open-paren count, track the range of counts still reachable. Two integers: low and high.”
7. Walk the per-character rule on the whiteboard: ( shifts both, ) shifts both down with a clamp, * widens.
8. “If high ever goes negative, every interpretation has an unmatched ) — return false. At the end, valid iff low == 0.”
9. Trace the second example ("(**))"). Show the band evolving to [0, 1] and landing at [0, 0].
10. “One pass, two integers, $O(n)$ time, $O(1)$ space. That’s what I’d ship.”

Summary

Valid Parenthesis String looks like a stack problem until the * arrives and every state branches three ways. The brute force is exponential. The DP over substrings is $O(n^3)$ and pays for itself only if you need to reconstruct an interpretation. The production answer is the greedy band: track the minimum and maximum reachable open-paren counts, widen on *, shift on literal brackets, fail early when the ceiling falls below zero, accept iff the floor ends at zero.

The lesson generalizes. When a decision cascade has commutative local choices and a single boolean question at the end, you almost never need to enumerate interpretations — you need to track the band of outcomes they could still reach. Internalize that move on this problem; it unlocks Jump Game, wildcard matching, and a long tail of “could this ever balance?” questions.