4.26.8 — Valid Parenthesis String

LeetCode 678 · Medium

The problem

A string contains (, ) and *. Each * may be treated as (, as ), or as an empty string. Return true if the string can be made valid.

"()"      →  true
"(*)"     →  true    (* as empty)
"(*))"    →  true    (* as an open bracket)
")("      →  false

The pattern

Without *, a single counter suffices: add one for (, subtract for ), fail if it goes negative, and require zero at the end. That is 4.8.1 Valid Parentheses with one bracket type.

Each * makes the count ambiguous — it could go up, down or stay. Trying all 3^n assignments is hopeless.

The fix:

Do not track the count. Track the range of counts that are still possible.

Two numbers:

• lo — the smallest open count possible, assuming every * so far was a closing bracket.
• hi — the largest, assuming every * was an opening bracket.

Then:

character	lo	hi
(	+1	+1
)	−1	−1
*	−1 (treat as ))	+1 (treat as ()

Fail when hi < 0. Even the most generous reading has more closers than openers, so no assignment can work.

Clamp lo at 0, never letting it go negative. A negative open count is meaningless — you cannot have −2 unmatched brackets — and it corresponds to an assignment that already failed. Clamping keeps lo describing only the assignments still alive.

At the end, lo == 0 means some assignment balances, because 0 lies within the reachable range.

Why every count in the range is reachable

This is the part that needs justifying, and it is why two numbers suffice rather than a set.

Flipping a single * from ) to ( changes the count by exactly 2 — but flipping it to empty changes it by 1. Since each * offers three consecutive values, the set of achievable counts at every position is a contiguous range, not a scattering. So the interval [lo, hi] describes it exactly.

That contiguity is what makes the algorithm valid. Without it you would need the whole set.

The solution

Python

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0

        for c in s:
            if c == '(':
                lo += 1
                hi += 1
            elif c == ')':
                lo -= 1
                hi -= 1
            else:                             # '*'
                lo -= 1                       # treat as ')'
                hi += 1                       # treat as '('

            if hi < 0:
                return False                  # too many closers, even at best
            lo = max(lo, 0)                   # a negative count is meaningless

        return lo == 0

TypeScript

function checkValidString(s: string): boolean {
  let lo = 0, hi = 0;

  for (const c of s) {
    if (c === '(') { lo++; hi++; }
    else if (c === ')') { lo--; hi--; }
    else { lo--; hi++; }

    if (hi < 0) return false;
    lo = Math.max(lo, 0);
  }

  return lo === 0;
}

The clamp must come after the hi < 0 check, not before, and it applies only to lo. Clamping hi would hide the failure condition entirely.

Return lo == 0, not hi == 0. hi being positive is fine — it just means some assignments left brackets open, and you only need one assignment to balance. lo == 0 says 0 is in the reachable range.

Trace

"(*))"

c	lo	hi	note
(	1	1
*	0	2	could be ), empty, or (
)	0 (clamped from −1)	1
)	0 (clamped from −1)	0

lo == 0 → true ✓. The valid reading is * as (, giving "(())".

And ")(":

c	lo	hi
)	0 (clamped)	−1 → return false

Complexity

O(n) time, O(1) space.

The two other solutions

Two stacks. Keep a stack of indices for ( and one for *. On ), match against an open bracket if possible, otherwise a star. At the end, pair leftover open brackets with leftover stars — and each star must come after the bracket it closes, which is why indices are stored rather than counts. O(n) time and space.

Two passes. Sweep left to right treating every * as ( and check the count never goes negative; then sweep right to left treating every * as ) and check the same. Both passing means valid. Also O(n) time and O(1) space, and it is a nice illustration of check the worst case from each direction.

Write the range version. It is the shortest and it generalises.

Where this goes next

• Minimum Add to Make Parentheses Valid — count the deficits from each side. Much simpler and a good warm-up.
• Minimum Remove to Make Valid Parentheses — two passes marking which brackets to delete.
• Longest Valid Parentheses — a stack of indices with a sentinel, or a DP.

The transferable idea: when a value becomes uncertain, track the interval of possibilities rather than branching. It appears in interval arithmetic, in constraint propagation, and in bounds analysis inside compilers — anywhere the exact value is unknown but its range is cheap to maintain.

What the interviewer will push on

"Why two counters?" Each * makes the open count ambiguous; the range of possible counts is contiguous, so its two endpoints describe it exactly.

"Why clamp lo at 0?" A negative open count corresponds to an already-failed assignment, and keeping it would understate the surviving possibilities.

"Why check hi < 0 and return false?" Even the most generous reading has too many closers.

"Why return lo == 0 rather than hi == 0?" You need one assignment to balance, and 0 being in the range says one does.

"Why is the reachable set contiguous?" Each * offers three consecutive values, so no gaps can form.

One thing to volunteer: name the technique — "instead of branching on each *, I carry the range of possible counts" — and say why the range has no holes. That is the insight; the code is four lines.

Next: 4.27 is the smallest group and the most mechanical — six problems where the only real decision is whether to sort by start or by end.