Valid Parenthesis String

Treat every * as ambiguous and track, at each position, the full set of open-parenthesis counts that are still achievable given some assignment of the *s seen so far. Recurse (with memoization) on (index, open_count): an open count going negative is a dead end, and reaching the end of the string is only valid if the open count is exactly 0.

from functools import lru_cache

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)

        @lru_cache(maxsize=None)
        def dp(i: int, open_count: int) -> bool:
            if open_count < 0:
                return False
            if i == n:
                return open_count == 0
            if s[i] == '(':
                return dp(i + 1, open_count + 1)
            elif s[i] == ')':
                return dp(i + 1, open_count - 1)
            else:
                return dp(i + 1, open_count + 1) or dp(i + 1, open_count - 1) or dp(i + 1, open_count)

        return dp(0, 0)

There are O(n) positions and O(n) possible open counts at each, giving O(n²) states, each doing O(1) work — O(n²) time and space.

Instead of tracking every individually achievable open count, only track the range [lo, hi] of open counts currently possible: lo is the smallest, hi is the largest, assuming every * so far has been assigned optimally. A '(' shifts both bounds up by one; a ')' shifts both down by one; a '*' widens the range by one on each side (it could be either bracket, or neither). If hi ever drops below 0, even the most generous assignment cannot recover — the string is invalid. If lo drops below 0, that just means some assignment keeps things non-negative even though others do not, so clamp lo to 0 rather than failing. At the end, 0 must be a reachable open count, i.e. lo == 0.

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0
        for c in s:
            if c == '(':
                lo += 1
                hi += 1
            elif c == ')':
                lo -= 1
                hi -= 1
            else:
                lo -= 1
                hi += 1
            if hi < 0:
                return False
            lo = max(lo, 0)
        return lo == 0

Tracing s = "(*))":

Why it’s correct: [lo, hi] is exactly the interval of open-parenthesis counts reachable by some assignment of the *s processed so far — and crucially, that interval is always contiguous (every integer between lo and hi is achievable, since each * only ever shifts or widens it by one). That means the interval alone is a lossless summary; no individual assignment needs to be remembered. Clamping lo at 0 is safe because a negative open count is never useful to preserve — an assignment that would drive it negative is simply not the one we care about, and there is always at least one assignment achieving lo’s clamped value or higher. If hi goes negative, every assignment has failed, so we can stop immediately. Complexity: one pass, two running variables → O(n) time, O(1) space.