LeetCode 678: Valid Parenthesis String

Problem Restatement

We are given a string s.

The string contains only three characters:

The wildcard '*' can be treated as one of three choices:

We need to return true if there is some way to replace every '*' so that the final string is a valid parenthesis string. Otherwise, return false.

A valid parenthesis string must satisfy the usual rules: every opening parenthesis must be matched by a later closing parenthesis, and every closing parenthesis must match an earlier opening parenthesis. The official problem defines '*' with these three possible meanings.

Input and Output

Example function shape:

def checkValidString(s: str) -> bool:
    ...

Examples

Example 1:

s = "()"

This is already valid.

Answer:

True

Example 2:

s = "(*)"

We can treat '*' as empty.

Then the string becomes:

()

Answer:

True

Example 3:

s = "(*))"

We can treat '*' as '('.

Then the string becomes:

(())

Answer:

True

Example 4:

s = ")*("

The first character is ')'.

There is no earlier '(' that can match it.

Answer:

False

First Thought: Try Every Replacement

A direct approach is to try every possible meaning of each '*'.

For each '*', we branch into three choices:

'*' -> '('
'*' -> ')'
'*' -> empty

After trying a replacement, we check whether the resulting parenthesis string is valid.

This works logically, but if there are many stars, the number of possibilities grows very quickly.

If there are k stars, there are:

3^k

possible replacements.

That is too expensive.

Key Insight

For ordinary parentheses, we can scan left to right and keep a count of unmatched opening parentheses.

For this problem, '*' makes the count uncertain.

Instead of keeping one count, we keep a range of possible counts.

Let:

After scanning part of the string, the actual number of unmatched opening parentheses could be any value between low and high.

The range changes like this:

But low cannot go below 0.

A negative number of unmatched opening parentheses does not make sense. If low becomes negative, we clamp it back to 0.

If high becomes negative, then even the most generous interpretation cannot provide enough opening parentheses. At that point, the string is impossible.

Algorithm

Initialize:

low = 0
high = 0

Then scan each character ch in s.

If ch == '(':

low += 1
high += 1

Both the minimum and maximum number of unmatched opens increase.

If ch == ')':

low -= 1
high -= 1

A closing parenthesis must consume one unmatched open.

If ch == '*':

low -= 1
high += 1

The minimum decreases because '*' may act as ')'.

The maximum increases because '*' may act as '('.

After each character:

if high < 0:
    return False

low = max(low, 0)

At the end, the string is valid if 0 is one possible unmatched-open count.

That means:

low == 0

Walkthrough

Consider:

s = "(*))"

Start:

At the end, low == 0, so the answer is true.

Now consider:

s = ")*("

Start:

high < 0, so there is no way to match the first closing parenthesis.

Return false.

Correctness

The algorithm maintains this invariant after each scanned prefix:

low is the smallest possible number of unmatched opening parentheses, and high is the largest possible number of unmatched opening parentheses, over all valid interpretations of '*' in that prefix.

At the start, before scanning anything, the only possible count is 0, so low = high = 0.

When the next character is '(', every possible interpretation gains one unmatched opening parenthesis. Therefore both bounds increase by one.

When the next character is ')', every possible interpretation must use one unmatched opening parenthesis. Therefore both bounds decrease by one. If high becomes negative, then even the largest possible number of opens was not enough, so no interpretation can be valid.

When the next character is '*', it may act as ')', empty, or '('. These choices can decrease the unmatched-open count by one, keep it unchanged, or increase it by one. Therefore the minimum possible count decreases by one, and the maximum possible count increases by one.

Because the number of unmatched opening parentheses cannot be negative, clamping low to 0 preserves the smallest meaningful possible count.

After the full string is scanned, the string can be valid exactly when zero unmatched opening parentheses is possible.

That is exactly the condition low == 0.

Therefore, the algorithm returns true if and only if the string can be interpreted as a valid parenthesis string.

Complexity

Let n be the length of s.

Implementation

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

        for ch in s:
            if ch == "(":
                low += 1
                high += 1
            elif ch == ")":
                low -= 1
                high -= 1
            else:
                low -= 1
                high += 1

            if high < 0:
                return False

            low = max(low, 0)

        return low == 0

Code Explanation

We start with:

low = 0
high = 0

These variables describe the possible range of unmatched opening parentheses.

For '(', both counters increase:

low += 1
high += 1

There is no choice here. An opening parenthesis always adds one unmatched open.

For ')', both counters decrease:

low -= 1
high -= 1

A closing parenthesis must match a previous opening parenthesis.

For '*', the range expands:

low -= 1
high += 1

The lowest case treats '*' as ')'.

The highest case treats '*' as '('.

Then we check:

if high < 0:
    return False

If high is negative, every possible interpretation has too many closing parentheses.

Finally:

low = max(low, 0)

This removes impossible negative lower bounds.

At the end:

return low == 0

If low is zero, then zero unmatched opening parentheses is possible, so the string can be valid.

Testing

def run_tests():
    s = Solution()

    assert s.checkValidString("()") is True
    assert s.checkValidString("(*)") is True
    assert s.checkValidString("(*))") is True
    assert s.checkValidString(")*(") is False

    assert s.checkValidString("*") is True
    assert s.checkValidString("(") is False
    assert s.checkValidString(")") is False

    assert s.checkValidString("((*)") is True
    assert s.checkValidString("(((******))") is True
    assert s.checkValidString("(((((*)))") is True
    assert s.checkValidString("(((((") is False

    print("all tests passed")

run_tests()

Test meaning: