Valid Parenthesis String

Problem

You are given a string s containing only the characters '(', ')', and '*'. Each '*' may be treated as a single '(', a single ')', or an empty string "". Decide whether there is some interpretation of the stars that makes s a valid parenthesis string.

A string is valid when every '(' has a matching ')' to its right, every ')' has a matching '(' to its left, and matches nest properly (equivalently: reading left to right, the running count of unmatched '(' never goes negative and ends at zero).

Return True if such an interpretation exists, otherwise False.

Examples

• s = "()" → True — already balanced.
• s = "(*)" → True — treat * as empty, leaving "()", which is valid.
• s = "(*))" → True — treat * as '(', giving "(())", which is valid.
• s = ")(" → False — the leading ')' has nothing to match and no star can fix it.

Constraints

• 1 <= len(s) <= 100
• s consists only of '(', ')', and '*'.
• Small input, so even an O(n^2) DP passes — but an O(n) greedy is the elegant target.

Think about it first

TL;DR

Track the range [lo, hi] of possible unmatched-open counts in one pass; valid iff hi never goes negative and lo returns to 0 — greedy, O(n) time, O(1) space.

Approach 1 — Brute force (try every meaning of every star)

Each '*' has 3 choices. Recurse over the string, branching at every star, and check if any full assignment yields a balanced string.

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

        def dfs(i: int, open_count: int) -> bool:
            if open_count < 0:               # a ')' had no match — prune
                return False
            if i == n:
                return open_count == 0
            c = s[i]
            if c == '(':
                return dfs(i + 1, open_count + 1)
            if c == ')':
                return dfs(i + 1, open_count - 1)
            # '*' → '(', ')', or empty
            return (dfs(i + 1, open_count + 1)
                    or dfs(i + 1, open_count - 1)
                    or dfs(i + 1, open_count))

        return dfs(0, 0)

Complexity: O(3^k) time where k is the number of stars, O(n) recursion depth. Correct but exponential.

Approach 2 — Dynamic programming (memoize on position + open count)

The insight: the recursion above only depends on (i, open_count), and open_count is bounded by n. Memoizing collapses the exponential tree to O(n^2) states.

from functools import lru_cache


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

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

        return dfs(0, 0)

Complexity: O(n^2) time and space (n positions × up to n open counts). Fine for n <= 100, and it makes the state space explicit — which the greedy below exploits.

Approach 3 — Greedy (track the interval of possible open counts)

Greedy-choice property (why one interval replaces the whole DP). At any prefix, the set of achievable “unmatched open” counts over all star assignments is a contiguous range of integers [lo, hi]: a '*' can nudge the count up by one, down by one, or leave it, so any value strictly between the extremes is also reachable by choosing intermediate star meanings. That means we never need the full DP table — the two endpoints lo and hi summarize every reachable state. Update rules per character:

• '(': lo += 1, hi += 1 (both interpretations forced up).
• ')': lo -= 1, hi -= 1.
• '*': lo -= 1 (star as ')'), hi += 1 (star as '(').

If hi < 0 at any point, then even treating every star as '(' leaves an unmatched ')' — no assignment can recover, so return False. We clamp lo at 0, because a negative minimum would mean “pretend we closed more than we opened,” which is illegal; the true minimum feasible open count can’t drop below zero. At the end the string is valid iff lo == 0, i.e. zero unmatched opens is within the still-feasible range.

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = 0   # min possible unmatched '('
        hi = 0   # max possible unmatched '('

        for c in s:
            if c == '(':
                lo += 1
                hi += 1
            elif c == ')':
                lo -= 1
                hi -= 1
            else:                # '*'
                lo -= 1
                hi += 1

            if hi < 0:           # too many ')' even if every '*' is '('
                return False
            if lo < 0:           # can't owe negative opens
                lo = 0

        return lo == 0

Walkthrough with s = "(*))":

Ends with lo == 0 → True. (Interpretation: the * acts as '(', giving "(())".)

Complexity: O(n) time, O(1) space — the classic optimal solution.

Common pitfalls

• Forgetting to clamp lo at 0. Without it, extra stars/')' would drive lo artificially negative and the final lo == 0 test would misfire. Clamping encodes “you can always choose a star to not close.”
• Returning hi == 0 or lo <= 0 at the end instead of lo == 0. You need zero to be inside the feasible range; since hi >= lo >= 0 always holds after clamping, lo == 0 is the exact condition.
• Checking hi < 0 only after the loop — it must be tested inside the loop, because an early irrecoverable ')' surplus must fail immediately.
• Treating '*' as only '('/')' and forgetting the empty-string option — the range [lo-1, hi+1] already covers “empty” as an in-between value.

Pattern takeaway

When a symbol introduces bounded uncertainty into a running quantity, don’t branch over every choice — track the feasible interval [min, max] of that quantity and update its two endpoints greedily. If the reachable set stays contiguous (as it does when each choice shifts the value by ±1 or 0), the two endpoints carry all the information the exponential search would, collapsing it to a single O(n) pass.