Problem Statement

Valid Parenthesis String

You are given a string s made of three kinds of characters: '(', ')' and '*'. Each '*' is a wildcard, meaning it can secretly be a '(', a ')', or nothing at all (an empty string). Your job is to return true if there is some way to fill in the wildcards so that every parenthesis matches up correctly, and false otherwise. "Matches up" means every '(' has a ')' that comes after it, like properly nested brackets. The tool we use here is a greedy range tracker. Instead of trying every possible meaning of every '*' (which would explode fast), we keep track of two numbers as we read left to right: the smallest number of unmatched '(' we could have so far, and the largest number we could have so far. Think of it as a thermometer with a low reading and a high reading. As long as the true count could fall somewhere in that range, we are still alive. We call the low number low and the high number high. If high ever drops below zero, that means even in the most generous case there are too many ')' with nothing to match them, so it is hopeless. If low drops below zero, we gently push it back up to zero, because we would simply choose not to use that many ')'. At the very end, if low can reach 0, a valid filling exists.

mediumStackGreedyGreedyTime: O(n) · Space: O(1)

Signals to notice

can string with * be valid parentheses* can be ( or ) or emptygreedy range tracking

Brute force first

Try all 3^k possibilities for each *. Exponential in the number of wildcards. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Track a range [minOpen, maxOpen] of possible open-paren counts. '(' increases both. ')' decreases both. '*' decreases min, increases max. Clamp min to 0. Valid if min can reach 0 at end. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `s="(*))"`

init: low=0, high=0
ch='(': low=1, high=1; high>=0 ok; clamp low=1
ch='*': low=0, high=2; high>=0 ok; clamp low=0
ch=')': low=-1, high=1; high>=0 ok; clamp low=0
ch=')': low=-1, high=0; high>=0 ok; clamp low=0
end: low==0 -> return true

What must stay true

minOpen = minimum possible unmatched '(' (treat * as ')'). maxOpen = maximum possible unmatched '(' (treat * as '('). If maxOpen < 0, too many ')'. If minOpen == 0 at end, it's valid. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

low, high = 0, 0
for ch in s:
    low  += (ch == '(') ? 1 : -1        # '*' acts like ')'
    high += (ch == ')') ? -1 : 1        # '*' acts like '('
    if high < 0: return false           # too many ')'
    low = max(low, 0)                    # clamp; '*' can be empty/')'
return low == 0

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only tracking one count — you need a range because '*' creates branching. The range collapses the exponential branches into two linear bounds. The fix is usually to return to the meaning of each move, not just the steps themselves.

Greedy Pattern