Valid Parenthesis String

GREEDY · MEDIUM

The problem

Given a string s made only of (, ), and *, decide whether it can be a valid parenthesization. The rules: every ( needs a matching ) that comes after it, every ) needs a matching ( that came before it, and each * is a wildcard — it may stand in for (, for ), or for nothing at all (an empty string). The question isn’t “is this string valid” — it’s “does SOME assignment of the * characters make it valid.”

Solution 1: Brute force — try every interpretation of every `*`

The direct reading of the problem is: each * has 3 possible interpretations, so try all of them. Recursively walk the string position by position; on a fixed ( or ) just keep going, but on a * branch into all 3 choices and recurse into each. If any branch reaches the end of the string with a balanced result, the whole string is valid. With k stars, that’s up to 3^k strings to check — genuinely exponential.

function isBalanced(str) {
  let bal = 0;
  for (const ch of str) { bal += ch === '(' ? 1 : -1; if (bal < 0) return false; }
  return bal === 0;
}

function checkValidStringBrute(s) {
  function dfs(i, path) {
    if (i === s.length) return isBalanced(path);
    const ch = s[i];
    if (ch === '(' || ch === ')') {
      return dfs(i + 1, path + ch);
    }
    // ch === '*' — try all 3 interpretations
    return dfs(i + 1, path + '(')
        || dfs(i + 1, path + ')')
        || dfs(i + 1, path);
  }
  return dfs(0, '');
}

Line by line:

i walks the ORIGINAL string s one position at a time; path holds the built-so-far result string, which can be shorter than i once a * is treated as empty.
Fixed characters have exactly one interpretation, so they just append and recurse — no branching, no waste.
A * branches into all 3 possibilities using ||. Because || short-circuits, the moment any branch returns true the remaining branches are never even tried — but in the worst case (no early success), all 3 branches per star run, compounding to 3^k.
isBalanced is only checked once i === s.length — exactly the same running-balance idea as Day 17’s Valid Parentheses, just applied after every * has already been committed to a specific interpretation.

Interactive visualization

Tracing s = "(**)" — watch the call stack grow and shrink as branches are explored and abandoned.

Press Play or Step to begin.

Step 0 / 23

This animation traces s = "(**)" — 4 characters, 2 stars, small enough to watch every branch, but already shows real backtracking: the first interpretation tried fails, and the search has to retreat and try another.

Complexity

Time	Space
O(3^k × n), k = number of ‘*’	O(n) recursion depth

Solution 2: Optimal — track a RANGE of possible open-paren counts

Instead of deciding what each * “is” up front, track a range of how many unmatched ( could currently be open: lo (the fewest, if every * so far that could help closes something or vanishes) and hi (the most, if every * so far opens something). A ( pushes both bounds up by 1; a ) pulls both down by 1; a * pulls lo down by 1 (it might close or vanish) but pushes hi up by 1 (it might open). Clamp lo at 0 — it can never mean “negative open parens,” it just means “this many or fewer is achievable, including zero.” If hi ever drops below 0, no interpretation can save the string — bail out immediately. At the end, the string is valid exactly when lo === 0 is achievable, meaning zero is somewhere inside the reachable range.

function checkValidStringOptimal(s) {
  let lo = 0, hi = 0;
  for (const ch of s) {
    if (ch === '(') { lo++; hi++; }
    else if (ch === ')') { lo--; hi--; }
    else { lo--; hi++; } // '*' — could close/vanish (lo) or open (hi)
    if (hi < 0) return false;   // even the best case has too many ')'
    if (lo < 0) lo = 0;         // can't have fewer than zero open parens
  }
  return lo === 0;
}

Line by line:

lo is the MINIMUM possible count of unmatched ( at this point — it assumes every * so far was as unhelpful as possible (a ) or empty).
hi is the MAXIMUM possible count — it assumes every * so far was as helpful as possible (an open paren).
if (hi < 0) return false — if even the MOST optimistic interpretation has gone negative, there’s no possible fix left; every other interpretation is at least as bad, so it’s safe to bail out immediately.
if (lo < 0) lo = 0 — clamping matters because lo going negative doesn’t mean “invalid,” it means “the low end of the achievable range is actually zero,” since a * can always choose NOT to over-close.
lo === 0 at the end means zero unmatched opens is somewhere inside the reachable [lo, hi] range — i.e., some assignment of every * balances the string exactly.

Interactive visualization

Tracing s = "(**)" — watch lo and hi update in the narration; there's no branching, just one pass.

Press Play or Step to begin.

Step 0 / 10

This animation traces the same s = "(**)" as above — watch lo and hi in the narration; there’s no branching this time, just one pass.

Complexity

Time	Space
O(n)	O(1)

Complexity comparison

Solution	Time	Space
Brute force (3-way backtracking per ‘*’)	O(3^k × n)	O(n)
Optimal (greedy lo/hi range tracking)	O(n)	O(1)

This is a genuine asymptotic improvement, not a constant-factor speedup. Brute force is exponential in the number of * characters — a string with 20 stars means up to 3^20 (over 3.4 billion) branches to explore. The greedy range-tracking pass is a single O(n) sweep regardless of how many stars appear, because it never actually commits to an interpretation for any individual * — it just tracks what’s still reachable.

Interview corner

Why is tracking a RANGE (lo/hi) enough, instead of tracking every individual possible count?

The set of open-paren counts reachable after processing a prefix is always a contiguous range of integers with the same parity pattern collapsing — every value between lo and hi is achievable by choosing some mix of interpretations for the stars seen so far.
So instead of tracking a whole set of possible counts, two numbers (the min and max) fully describe everything that’s reachable.
Each new character shifts and/or widens that range in a simple, uniform way — no set data structure needed.

Why does hi < 0 justify failing immediately, without checking any other branch?

hi is already the MOST optimistic count achievable — every other interpretation of the stars seen so far produces a count less than or equal to hi.
If even the best case has gone negative (more ) than could possibly be matched), every worse case has too, so there’s nothing left to explore.

How would you extend this to also RETURN one valid assignment of the stars, not just true/false?

The greedy range trick alone doesn’t recover a witness assignment directly — it only proves existence.
One approach: run the brute-force backtracking with memoization on (i, openCount) pairs, returning the actual path the moment a valid one is found — it stays polynomial because the state space is bounded by n × n pairs instead of 3^k branches.

Trick question — what does this log?

function attempt(label, fn) {
  console.log('trying', label);
  return fn();
}
const result = attempt('(', () => false)
            || attempt(')', () => true)
            || attempt('empty', () => true);
console.log('result:', result);

Logs: trying (, then trying ), then result: true — "trying empty" is never logged.
|| short-circuits: once attempt(')', ...) returns a truthy value, JavaScript never evaluates the third operand at all.
⚠ Trap: this is exactly what happens inside checkValidStringBrute’s dfs(...) || dfs(...) || dfs(...) line — the moment one interpretation of a * succeeds, the remaining interpretations are never explored. It’s why the worst-case bound is 3^k rather than the actual runtime on every input — a lucky early success can make the brute force finish almost instantly, while an unlucky (or invalid) input forces it through every branch.

Quiz

Why is the brute-force solution’s worst case O(3^k) for k stars, not O(2^k)?
- a) Each ‘*’ branches into 3 interpretations — ‘(’, ‘)’, and empty — not 2
- b) Each ‘*’ only ever branches into ‘(’ or ‘)’, never empty
- c) It depends on the total string length, not the number of stars
What do lo and hi represent at any point in the optimal scan?
- a) The minimum and maximum possible counts of currently-unmatched open parens, given every way the stars seen so far could be interpreted
- b) The index of the first and last ‘*’ character in the string
- c) The shortest and longest valid string that could be built from s
Why does the optimal solution clamp lo at 0 instead of letting it go negative?
- a) A negative lo would just mean “zero is still achievable” — since a ‘*’ can always choose to not over-close, the real lower bound can’t go below zero
- b) Negative numbers would cause a runtime error in JavaScript
- c) Clamping lo has no effect on the final answer either way
Why does hi < 0 mean the string can be rejected immediately, without exploring other interpretations?
- a) hi is already the best-case (highest) count achievable — if even that has gone negative, no interpretation of the stars seen so far can recover
- b) hi going negative is actually a bug and should never happen on valid input
- c) Only lo matters for early termination, hi is checked only at the very end
What’s the fundamental reason the optimal solution avoids the brute force’s exponential blowup?
- a) It never commits to a specific interpretation for any ‘*’ — it tracks a range of possibilities and updates that range in O(1) per character
- b) It works on a different, smaller version of the input string
- c) It caches every previous string it has ever checked

Valid Parenthesis String

The problem

Solution 1: Brute force — try every interpretation of every *

Interactive visualization

Complexity

Solution 2: Optimal — track a RANGE of possible open-paren counts

Interactive visualization

Complexity

Complexity comparison

Interview corner

Quiz

Solution 1: Brute force — try every interpretation of every `*`