Greedy crash course ↗ · 87

678. Valid Parenthesis String

A string of (, ), and * is valid if the stars can be replaced so parentheses balance. Track a [low, high] range of possible open-paren counts — if 0 is ever reachable at the end, the string is valid.

● MediumGreedyTwo-pointer rangeStack alternativeTypeScript

PROBLEM What we're solving

Given a string containing only (, ), and *, return true if it can be a valid parenthesis sequence. * can represent an open paren, a close paren, or an empty string. Concrete example: s="(*) " → true (replace * with ) giving (), or with empty giving () — either works). Another: s="(*)" → true. But s=")(*)" → false.

KEY IDEA Track a range, not a single count

Insight → instead of enumerating every possible assignment for *, track the interval [low, high] of open-paren counts that are still achievable. low is the minimum (treat every * as ) or empty); high is the maximum (treat every * as (). The string is valid iff 0 falls in the reachable range at the end — i.e. low === 0 after processing everything.

RECIPE Widen or narrow the window, then check if 0 survives

0 · Initialize. low = 0, high = 0 — before seeing any char, exactly 0 opens are open.
1 · On (. Both bounds increase: every live scenario gains one open paren. low++; high++.
2 · On ). Both bounds decrease. Then clamp lowat 0 (an open count can't be negative — no valid scenario has a deficit). If high < 0, even the most optimistic scenario has more closes than opens: return false immediately.
3 · On *. The wildcard widens the window: high++ (best case: use it as () and low-- (best case: use it as ) or empty). Clamp low at 0 for the same reason as step 2.
4 · At the end. Return low === 0. If the minimum achievable open count is 0, we can always close everything.

Classic confusion → beginners check low === 0 but forget to clamp low to 0 during the scan. Without the clamp, low can go negative, meaning the range always contains 0 and the function never returns false — even for strings like ")".

COST Complexity & alternatives

Backtracking / enumerate all *

O(3ⁿ)

Try each * as (, ), or empty — exponential blowup.

Greedy [low, high] range

O(n)

Single pass, O(1) space. Optimal.

Stack alternative

You can also solve this with two stacks: one holding indices of unmatched ( and one for *. After the scan, greedily match leftover ( with * to the right of each. Both approaches are O(n) time but the stack uses O(n) space, while the range approach uses O(1).

Pattern transfer → the "track a feasible range" trick appears in Minimum Add to Make Parentheses Valid (track net deficit), Minimum Number of Swaps to Make the String Balanced, and any problem where a wildcard/variable choice widens a set of reachable states — rather than branching on each choice, collapse the reachable set into a scalar interval.

RUN IT Track [low, high] range of open counts

s =

step 0 / 4

STARTTrack the range of possible open-count values [low=0, high=0]. We scan each character and widen or narrow the window.

1function checkValidString(s: string): boolean {
2▶  let low = 0;   // minimum possible open-paren count
3▶  let high = 0;  // maximum possible open-paren count
4 
5  for (const ch of s) {
6    if (ch === '(') {
7      low++;
8      high++;
9    } else if (ch === ')') {
10      low--;
11      high--;
12    } else {          // ch === '*'
13      low--;           // treat '*' as ')' or empty: shrink floor
14      high++;          // treat '*' as '(':  grow ceiling
15    }
16    if (high < 0) return false;  // even best case has too many ')'
17    if (low < 0) low = 0;        // floor can't go below 0
18  }
19 
20  return low === 0;  // best case closes all '('
21}

(0*1)2

State

—

low

high

width

clamped

( → both bounds up) → both bounds down* wildcard / validinvalid / fail

slowfast

TYPESCRIPT The solution, annotated

checkValidString.ts
function checkValidString(s: string): boolean {
  let low = 0;   // minimum possible open-paren count
  let high = 0;  // maximum possible open-paren count

  for (const ch of s) {
    if (ch === '(') {
      low++;
      high++;
    } else if (ch === ')') {
      low--;
      high--;
    } else {          // ch === '*'
      low--;           // treat '*' as ')' or empty: shrink floor
      high++;          // treat '*' as '(':  grow ceiling
    }
    if (high < 0) return false;  // even best case has too many ')'
    if (low < 0) low = 0;        // floor can't go below 0
  }

  return low === 0;  // best case closes all '('
}

Reading it block by block

Lines 2–3 — initialize the range. low and high both start at 0: before seeing any character, the only reachable open-paren count is 0.

Lines 6–17 — scan each character. For (: both bounds grow by 1 (this is a forced open). For ): both shrink by 1 (forced close). For *: high grows (optimistic: treat as () and low shrinks (pessimistic: treat as ) or empty).

Line 18 — early exit. If high < 0, even the most favorable assignment of wildcards can't prevent the close count from exceeding the open count. Return false immediately.

Line 19 — clamp low. low represents the minimum feasible open-paren count. It can never be negative (no valid execution has a deficit of opens), so clamp it: if (low < 0) low = 0. Forgetting this clamp is the single most common bug.

Line 22 — final check. After the full scan, low === 0 means there exists at least one assignment of * characters that leaves zero unmatched open parens — i.e. a valid sequence. If low > 0, even the most close-heavy assignment still leaves opens unmatched.

Complexity → O(n) time — one linear scan. O(1) space — only two integer variables. The stack-based alternative also runs in O(n) time but uses O(n) extra space.

INTERVIEWFollow-ups they'll ask

"Can you solve it with a stack?" Yes — maintain a stack for unmatched ( indices and another for * indices. After scanning, pair leftover ( with a * that appears to its right. O(n) time, O(n) space.
"What if * can only be ( or ) — not empty?" The range shrinks: low and high both move by exactly ±1 on *, so it behaves identically to knowing which one to choose — but you'd lose the "empty" escape hatch. Handle by adjusting the wildcard rule in the range update.
"Return one valid assignment of * characters." Record which choice you make for each * in two passes: forward to detect where a close is needed, backward to confirm opens — then reconstruct the assignment.
"What edge cases matter?" Empty string (trivially valid), all-star string of length n (valid — replace with balanced parens or all empty), a leading )(immediately sets high < 0 → false), and an unclosed (with no wildcards (low stays > 0 → false).
"Minimum number of insertions to make s valid?" Closely related: count the minimum operations needed using a similar open-balance counter, accumulating deficit each time a ) finds no match.

OPTIMAL Greedy

checkValidString.ts
function checkValidString(s: string): boolean {
  let low = 0;   // minimum possible open-paren count
  let high = 0;  // maximum possible open-paren count

  for (const ch of s) {
    if (ch === '(') {
      low++;
      high++;
    } else if (ch === ')') {
      low--;
      high--;
    } else {          // ch === '*'
      low--;           // treat '*' as ')' or empty: shrink floor
      high++;          // treat '*' as '(':  grow ceiling
    }
    if (high < 0) return false;  // even best case has too many ')'
    if (low < 0) low = 0;        // floor can't go below 0
  }

  return low === 0;  // best case closes all '('
}

Complexity → O(n) time — one linear scan. O(1) space — only two integer variables. The stack-based alternative also runs in O(n) time but uses O(n) extra space.

ALT 1 Brute force — try every meaning of each *

O(3ⁿ) time · O(n) space

Recurse character by character, tracking the running open count; at each * branch into all three choices — (, ), or empty — and accept if any branch ends balanced.

approach-2.ts
function checkValidString(s: string): boolean {
  // open = number of unmatched '(' so far. Recurse over each character.
  const dfs = (i: number, open: number): boolean => {
    if (open < 0) return false;            // a ')' had no matching '('
    if (i === s.length) return open === 0; // valid iff nothing left open
    const ch = s[i];
    if (ch === '(') return dfs(i + 1, open + 1);
    if (ch === ')') return dfs(i + 1, open - 1);
    // ch === '*': treat as '(', ')' or empty.
    return dfs(i + 1, open + 1) || dfs(i + 1, open - 1) || dfs(i + 1, open);
  };

  return dfs(0, 0);
}

Note → Every * triples the branching, so a string of all stars explodes to 3ⁿ leaves. Memoizing on (i, open) collapses it to O(n²); the greedy [low, high] range does the same job in a single O(n) pass with O(1) space.

MNEMONIC The one-liner

"low is the floor of opens (clamp at 0), high is the ceiling — * widens both ends. If high goes negative, bail. If low reaches 0 at the end, you're valid."

TRIGGERS When you see _ → reach for _

"( ) and * wildcard — is it balanced?"	[low, high] open-count range
wildcard can be one of several chars	track a feasible interval, not a single value
parentheses validity with optional chars	greedy range + high<0 early exit
"minimum insertions / swaps for balance"	open-count balance variable + deficit accumulator

SKELETON The reusable shape

skeleton.ts
let low = 0, high = 0;
for (const ch of s) {
  if (ch === '(')      { low++; high++; }
  else if (ch === ')') { low--; high--; }
  else                 { low--; high++; }  // '*'
  if (high < 0) return false;
  if (low < 0)  low = 0;
}
return low === 0;

FLASHCARDS Tap to flip

What do low and high represent?

low: minimum possible open-paren count (treating * as ) / empty). high: maximum (treating * as ().

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does high < 0 during the scan tell you?

QUESTION 02

For s="(*)", what are [low, high] after processing all three characters?

QUESTION 03

Why must low be clamped to 0 after each step?

QUESTION 04

What is the time complexity of the greedy [low, high] approach?

QUESTION 05

s=")" — what happens on the first character?

QUESTION 06

The final check is return low === 0. Why not low <= 0?

QUESTION 07

Which string correctly describes what low === 0 at the end means?

QUESTION 08

#678 · Valid Parenthesis StringTrack a range [lo, hi] of possible open-paren counts as you scan. "(" increments both, ")" decrements both, "*" widens the range. Clamp lo at 0; the string is valid if lo ever reaches 0 at the end.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Track a range, not a single count

RECIPE Widen or narrow the window, then check if 0 survives

COST Complexity & alternatives

Stack alternative

RUN IT Track [low, high] range of open counts

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Greedy

ALT 1 Brute force — try every meaning of each *

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _