MEDIUM

Valid Parenthesis String

Given a string s made only of '(', ')', and '*' — where each '*' can stand in for '(', ')', or an empty string — return true if some interpretation of the '*'s makes s a valid parentheses string.

Example

Input s = "(*))"

Output true

Key Pointers

Trying every interpretation of each '*' is exponential — instead track a range [loMin, hiMax] of possible open-paren counts as you scan.
'(' raises both bounds, ')' lowers both, and '*' lowers the low bound while raising the high bound — covering all three interpretations in one step.
loMin can never go below 0 (clamp it back up); if hiMax ever drops below 0, no interpretation can recover and the answer is false immediately.

Step-by-Step Analysis

Initialize loMin = 0, hiMax = 0.
For each character c: if '(', increment both bounds; if ')', decrement both; if '*', decrement loMin and increment hiMax.
If hiMax < 0 at any point, return False.
Clamp loMin to 0 whenever it goes negative.
After the scan, return True if loMin == 0, else False.

Complexity

Time: O(n) — Space: O(1)

Code

def checkValidString(s: str) -> bool:
    loMin, hiMax = 0, 0

    for c in s:
        if c == "(":
            loMin += 1
            hiMax += 1
        elif c == ")":
            loMin -= 1
            hiMax -= 1
        else:
            loMin -= 1
            hiMax += 1

        if hiMax < 0:
            return False
        loMin = max(loMin, 0)

    return loMin == 0

Code Explanation

How the solution above works, piece by piece.

Instead of trying every choice for *, track the range of possible open-bracket counts: loMin (fewest) to hiMax (most).
( raises both; ) lowers both; * could be ), empty or (, so it lowers loMin and raises hiMax.
If even the maximum drops below 0, there are too many ) no matter what → False.
A negative minimum just means some choices were bad, so clamp loMin at 0.
At the end, valid if 0 open brackets is possible: loMin == 0. O(n) time, O(1) space.

Visual Walkthrough

Running it on s = "(*))":

Each row is the [min, max] range of unmatched ( after that character. The range never goes fully negative, and 0 is inside it at the end, so the string can be valid (the * acts as ().

Video Explanation

NeetCode — LeetCode 678