LeetCode #678 Medium

Valid Parenthesis String

A string contains (, ), and , where may act as (, ), or an empty string. Return whether the string can be made valid.

greedystringsstack

Open on LeetCode ↗

02

Intuition

💡

Without wildcards a single counter suffices, and reaching for one here is the natural mistake — after ( the open count could be 0, 1, or 2 at the same time, so any single number you commit to will be wrong later. Track the range instead: low assumes every star is the least helpful choice, high the most. The string is valid if that range can land on zero. One detail carries the whole thing: clamp low at 0, because an open-bracket count cannot go negative, and without the clamp valid strings like () fail.

03

Approach

1

See why one counter is not enough

Reading (* , the number of open brackets could be 0, 1, or 2 depending on how the star is used. A single counter must commit to one value and will be wrong later. Recursing over the three choices per star is O(3^n), and memoising it gives an O(n^2) DP that works but is far more code than needed.

2

Track an interval instead

Let low be the count if every star so far were a closing bracket, and high the count if every star were an opening one. A ( raises both, a ) lowers both, and a * lowers low and raises high — widening the range by one in each direction. Every achievable count lies between them.

3

Clamp low, fail on high, and check the end

If high ever goes negative there are too many closers even in the most generous reading, so return false immediately. If low goes negative, clamp it to 0 — a count of open brackets can never be negative, and the stars responsible can simply be treated as empty instead. At the end return low == 0, meaning some assignment closes every bracket exactly. One pass, O(n) time, O(1) space.

04

Solution & live demo

python

▶1class Solution:
▶2    def checkValidString(self, s):
▶3        low = high = 0
▶4        for ch in s:
▶5            if ch == '(': 
▶6                low += 1
▶7                high += 1
▶8            elif ch == ')':
▶9                low -= 1
▶10                high -= 1
▶11            else:
▶12                low -= 1
▶13                high += 1
▶14            if high < 0:
▶15                return False
▶16            low = max(low, 0)
▶17        return low == 0

05

Edge cases

All stars

Every star can be empty, so low stays clamped at 0 and the answer is true.

Leading close bracket, e.g. ")("

high goes negative on the first character, returning false at once.

Forgetting to clamp low

low drifts negative and the final low == 0 test fails on valid strings like "(*)".

Unmatched opens, e.g. "(((*)"

low ends above 0, so no assignment balances the string and false is correct.

06

Complexity

Time

O(n)

Space

O(1)

Two integers replace an O(n^2) DP or an O(3^n) search.