Valid Parenthesis String

MediumGreedy rangeLeetCode 678 ↗World 7-12

0:00 / 0:00

Check brackets where each star can be open, close or nothing. Track the lowest and highest possible open count instead of choosing.

▼

The problem

LeetCode 678 (Medium). Given a string of (, ) and *, where each * can be an open bracket, a close bracket or the empty string, return whether some choice of the stars makes the string a valid bracket sequence.

Examples (LeetCode's): "()" → true, "(*)" → true (the star is nothing), "(*))" → true (the star opens).

TRY IT ON LEETCODE ▶

The solution

def checkValidString(s):
    lo = hi = 0
    for c in s:
        if c == '(':
            lo, hi = lo + 1, hi + 1
        elif c == ')':
            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

Transcript

Valid Parenthesis String. You get a string of open brackets, close brackets and stars. A star is a wild card: it can be an open bracket, a close bracket, or nothing. Can you pick the stars so the brackets balance?

Open, close is valid. Open, star, close is valid: the star becomes nothing. Open, star, close, close is valid too: this time the star opens.

The easy way tries all three choices per star. With k stars, that's three to the k strings. A table over position and open count is better, but still order n squared.

The greedy trick: don't choose yet. Keep the range of open counts you could have, low to high. An open bracket raises both, a close lowers both, and a star stretches the range: low goes down, high goes up. If high drops below zero, there are too many closes: fail. Low never drops below zero. At the end, low must be zero.

In code, low and high start at zero. Each character moves them. If high is negative, return false. Clamp low at zero, and return whether low is zero.

Try open, star, close, close. Open: one and one. Star: zero and two. Close: low would be minus one, so it stays zero, and high is one. Close: zero and zero. Low ends at zero, so it's valid. But open, open, star ends with low at one: a bracket can never close. False.

One pass and two numbers: order n time, order one space.

Don't choose, keep the range. That's Valid Parenthesis String.