LeetCode 678 · Greedy

Valid Parenthesis String, explained with a picture

Brackets with wildcard stars.

MediumGreedy
▶ Watch it step by step

The problem

A string has "(", ")" and "*". A star can be "(", ")" or nothing. Can the string be a valid bracket string?

Input:  "(*))"
Output: true   (the star acts as "(")

Picture it

Instead of trying every choice for every star, track a range: the fewest and the most brackets that could still be open. "(" raises both, ")" lowers both, and "*" lowers the minimum and raises the maximum. If the maximum ever goes negative, too many closers. The minimum is never allowed below 0. At the end, a minimum of 0 means it can be valid.

How to recognise it

  • It is the "valid brackets" check, but with a wildcard * that can be (, ) or nothing.
  • The ordinary solution is a running balance that never drops below zero and ends at zero. The wildcard turns that single number into a range of possible balances.
  • Up to 100 characters, with possibly many stars: choosing a meaning for each star one by one branches 3 ways each time.
  • Whenever a choice at each step only moves a counter by a fixed amount, track the smallest and largest values it could have instead of every choice.

Start with brute force

Try all three meanings of every star (3^k combinations for k stars), and check each resulting string with a plain balance counter.

def valid_brute(s, options=("(", ")", "")):
    stars = [i for i, c in enumerate(s) if c == "*"]
    for pick in product(options, repeat=len(stars)):
        t = list(s)
        for i, p in zip(stars, pick):
            t[i] = p
        bal = 0; ok = True
        for c in t:
            bal += 1 if c == "(" else -1 if c == ")" else 0
            if bal < 0:
                ok = False; break
        if ok and bal == 0:
            return True
    return False

With k stars there are 3^k strings, each checked in O(n). Ten stars is 59,049 strings, and a string of 100 stars would need about 5 × 10^47. Space is O(n) for the rebuilt string.

From brute force to the idea

  1. Think in balances. After each character, the number of unmatched ( can be many different values depending on what the stars were. Only the lowest and highest possible values matter, because every value in between is also possible.
  2. Update the range. A ( raises both lo and hi by 1. A ) lowers both by 1. A * could be ) (lowers), nothing, or ( (raises), so lo drops by 1 and hi rises by 1.
  3. Too many closers. If hi < 0, even the most helpful stars cannot make the string valid: too many ) have come. Return False immediately.
  4. Clamp the low end. A balance below 0 is not allowed, so the lowest useful value is 0: lo = max(lo, 0). This means the star was treated as nothing (or () when it would have gone negative.
  5. Finish. At the end, the string is valid if 0 is a possible balance, which (given the clamp) means lo == 0.

This is the key idea: keep the range of possible open-bracket counts, fail if its top goes below zero, and succeed if its bottom reaches zero at the end.

The key idea

Greedy with (lo, hi) open-count bounds. O(n), O(1) memory.

Python solution

def check_valid_string(s):
    lo = hi = 0                        # range of possible open brackets
    for ch in s:
        if ch == "(":   lo, hi = lo + 1, hi + 1
        elif ch == ")": lo, hi = lo - 1, hi - 1
        else:           lo, hi = lo - 1, hi + 1   # * could be ), nothing, or (
        if hi < 0:
            return False                # too many ) whatever the stars are
        lo = max(lo, 0)
    return lo == 0

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n × 3^k): every star assignment is built and scannedO(n): the rebuilt string
Range of balances (shown code)O(n): one pass with a few additions per characterO(1): two integers

Edge cases

  • Empty string: returns True.
  • Only a star ("*"): returns True (the star is nothing).
  • Lone brackets ("(", ")"): both return False.
  • Wrong order (")("): returns False; hi becomes −1 at the first ). "*(" also returns False, since the final ( stays open.
  • A star as a closer ("(*)" and "(*))"): both return True (the second makes the star a ().
  • A star as an opener ("(*", "*)"): both return True.
  • Only stars ("****"): returns True.

Common mistakes

  • Dropping the clamp lo = max(lo, 0): "(*)" then returns False, because lo ends at −1.
  • Returning lo == hi or hi == 0 at the end instead of lo == 0.
  • Checking lo < 0 for failure instead of hi < 0. A low lo can be repaired by stars; a low hi cannot.
  • Treating every star as ( in a single check, which fails "(*)"; treating every star as ) fails "*)".
Your turn: stars cannot be nothing

Now each * must become exactly ( or ) (it cannot be empty). Is the string valid? For "(*)" the answer is False and for "(*))" it is True. Describe your approach, then write it if you like.

Compare with our answer

Every star now changes the balance by exactly one, so the length must be even (an odd length can never end at 0). The range update itself stays the same.

def check_star_not_empty(s):
    if len(s) % 2:
        return False
    lo = hi = 0
    for ch in s:
        if ch == "(":   lo, hi = lo + 1, hi + 1
        elif ch == ")": lo, hi = lo - 1, hi - 1
        else:           lo, hi = lo - 1, hi + 1
        if hi < 0:
            return False
        lo = max(lo, 0)
    return lo == 0

check_star_not_empty("(*))") is True, check_star_not_empty("(*)") is False and check_star_not_empty("**") is True. Time O(n), space O(1).

A strong answer mentions: the extra parity test (an odd length can never balance), reusing the lo/hi range, and why the same update still works.

Check what stuck

1. A message contains (, ) and wildcard * characters, where a wildcard may be (, ) or nothing, and the message has up to 100 characters. Which approach fits best?

2. What does a ) do to the range, and why does hi < 0 mean failure?

3. A learner deletes the line lo = max(lo, 0). For which input does the function now return the wrong answer?

Score 60% or more and the lesson is marked complete.