Valid Parenthesis String: Greedy Range Tracking

Valid Parenthesis String is LeetCode problem 678, rated Medium. You are given a string containing only three characters: (, ), and *. The wildcard * can represent an open parenthesis (, a close parenthesis ), or an empty string. Your job is to determine whether the string can be valid, meaning every open parenthesis has a matching close and vice versa.

The trick is that each * introduces three possible futures. Trying all combinations would be exponential. Instead, you can track the range of possible open-parenthesis counts and decide validity in a single left-to-right scan.

The greedy range approach

The key insight is that you do not need to know which specific choice each * makes. You only need to know whether some valid assignment exists. You can track this with two variables:

• lo: the lowest possible number of unmatched open parentheses
• hi: the highest possible number of unmatched open parentheses

For each character:

• ( increases both lo and hi by 1 (one more open paren no matter what).
• ) decreases both lo and hi by 1 (one fewer open paren no matter what).
• * decreases lo by 1 (if we treat it as )) and increases hi by 1 (if we treat it as (). Treating it as empty falls in between.

After updating, you clamp lo to a minimum of 0, because you can never have a negative count of open parentheses. If hi ever drops below 0, that means even the most optimistic interpretation cannot keep the string valid, so you return false immediately.

At the end, if lo is 0, some assignment makes the string valid. If lo is greater than 0, there are too many unmatched opens no matter what.

The solution

def checkValidString(s: str) -> bool:
    lo = 0
    hi = 0

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

        if hi < 0:
            return False

        lo = max(lo, 0)

    return lo == 0

Walking through an example

Let's trace through the string "(*)":

1. Initialize: lo=0, hi=0. No characters processed yet.
2. Index 0, (: Both lo and hi go up by 1. Now lo=1, hi=1. We definitely have one unmatched open.
3. Index 1, *: lo decreases by 1 (treating * as )), hi increases by 1 (treating * as (). Now lo=0, hi=2. The range [0, 2] means we might have 0, 1, or 2 unmatched opens depending on what * becomes.
4. Index 2, ): Both lo and hi decrease by 1. lo goes to -1, clamped to 0. hi goes to 1. Range is [0, 1].
5. Final check: lo is 0, so a valid assignment exists. For instance, treating * as empty gives "()", which is valid.

If we tried the string "(*)))", hi would drop below 0 before we finish, and we would return false. If we tried "(((*", lo would be 2 at the end (not 0), meaning too many unmatched opens remain regardless of the wildcard choices.

Complexity

We scan the string once, updating two integer variables at each step. No auxiliary data structure is needed, so space is constant. The time is linear in the length of the string.

A dynamic programming approach also works (tracking which open counts are reachable at each index), but it takes O(n^2) time and O(n) space. The greedy range method compresses that DP state into just two numbers.

Edge cases

• Empty string: lo and hi remain 0. An empty string is trivially valid.
• All wildcards: "***" is valid because you can treat every * as empty. lo stays at 0 through clamping.
• No wildcards: The problem reduces to the classic valid parentheses check. lo and hi always equal each other.
• Single close first: ")*" makes hi go to -1 at the first character, so you return false immediately. No wildcard can fix an unmatched ) that appears before any ( or *.

The building blocks

Range tracking instead of enumeration

When a problem has branching possibilities (like a wildcard that could be three things), you do not need to explore every branch. If the only thing that matters is whether some branch succeeds, tracking the min and max of a single variable collapses exponential possibilities into a constant-space summary. This same idea appears in interval-based reasoning problems.

Greedy clamping

Clamping lo to 0 is a subtle but critical step. Without it, lo could go negative, and subsequent ( characters would "use up" that negativity in a way that does not correspond to any real assignment. Clamping enforces the invariant that every state in the range [lo, hi] represents a physically possible open count.

Left-to-right invariant maintenance

The algorithm maintains a loop invariant: at every step, the range [lo, hi] exactly describes which open counts are achievable given the characters seen so far. Each character update preserves this invariant. This pattern of maintaining a tight invariant through a linear scan shows up across many greedy problems, from gas station to jump game.

From understanding to recall

The core thing to memorize here is the two-variable framework: lo tracks the minimum possible open count, hi tracks the maximum. Each character type has a deterministic effect on both. The two special rules to internalize are: clamp lo to 0 after each step, and bail out early if hi drops below 0. If you can recall these rules, the code writes itself in under a minute.

Practice reconstructing the algorithm from the principle: "track the range of possible open counts." That single sentence should be enough to regenerate the entire solution. Spaced repetition will help you lock it in so the pattern is available the next time you see a problem with wildcard matching or branching possibilities.

Related posts

• Valid Parentheses - the classic stack-based parenthesis matching problem that builds the foundation for this one
• Longest Valid Parentheses - extends parenthesis validation to finding the longest valid substring using index tracking
• Generate Parentheses - explores the space of all valid parenthesis combinations using backtracking