Valid Parenthesis String

Description

Check whether a string of (, ), and * can become balanced by treating each star as an opening parenthesis, closing parenthesis, or empty string.

Solution

def check_valid_string(s):
    low = 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(0, low)
    return low == 0

Examples

Approach

Track the lowest and highest possible unmatched opening counts after each prefix. A star decreases the lower bound and increases the upper bound; clamp the lower bound to zero. A negative upper bound is impossible, and a final lower bound of zero means some interpretation balances.