159 — Valid Parenthesis String

159 — Valid Parenthesis String

LeetCode 678 · Medium. Given a string s containing only three kinds of characters: '(', ')', and '*', return true if s is valid. The validity rules are: any '(' must have a matching ')', any ')' must have a matching '(', and any '*' may be treated as a single '(', a single ')', or an empty string.

---

🍽️ Intuition

Without the * wildcards, this would just be ordinary bracket matching — track a single open-paren count and make sure it never goes negative and ends at zero. The * characters make that single count ambiguous, since each one could be any of three things. Rather than picking one interpretation and hoping, track a whole range of possible open-paren counts at once: the smallest it could be (treating every ambiguous * as pessimistically as possible) and the largest it could be (treating every * as optimistically as possible). As long as that range never becomes entirely invalid — the high end never dips below zero, and the low end never needs to go below zero either (it just clamps at zero, since treating a * as empty is always available as a fallback) — there's some valid interpretation, and the string is valid exactly when zero is achievable at the very end.

---

🚩 Pattern-Recognition Cue

"Wildcard character that can act as one of several tokens, check overall validity" is the range-tracking greedy tell: instead of branching on every ambiguous choice, track the minimum and maximum possible value of the running state (here, open-paren count) in a single pass, failing only when the maximum goes negative and succeeding only when the minimum can reach exactly zero at the end.

---

🐢 Brute Force

Recursively try all three interpretations of every *, tracking the exact open-paren count along each branch.

func checkValidStringBruteForce(_ s: String) -> Bool {
    let chars = Array(s)

    func isValid(_ index: Int, _ openCount: Int) -> Bool {
        if openCount < 0 { return false }
        if index == chars.count { return openCount == 0 }

        switch chars[index] {
        case "(":
            return isValid(index + 1, openCount + 1)
        case ")":
            return isValid(index + 1, openCount - 1)
        default: // '*'
            return isValid(index + 1, openCount + 1) ||   // treat as '('
                   isValid(index + 1, openCount - 1) ||   // treat as ')'
                   isValid(index + 1, openCount)          // treat as empty
        }
    }

    return isValid(0, 0)
}

// smoke test
print(checkValidStringBruteForce("()"))     // true
print(checkValidStringBruteForce("(*)"))    // true
print(checkValidStringBruteForce("(*))"))   // true
print(checkValidStringBruteForce("(((")) // false

Big-O: O(3^n) time in the worst case — every * branches three ways. O(n) space for the recursion stack.

---

🚀 Optimal

Track the minimum and maximum possible open-paren count in a single pass, clamping the minimum at zero (an ambiguous * can always fall back to "empty") and failing immediately if the maximum ever goes negative.

func checkValidString(_ s: String) -> Bool {
    var loCount = 0   // smallest possible number of unmatched open parens
    var hiCount = 0   // largest possible number of unmatched open parens

    for char in s {
        switch char {
        case "(":
            loCount += 1
            hiCount += 1
        case ")":
            loCount -= 1
            hiCount -= 1
        default: // '*'
            loCount -= 1   // pessimistic: treat as ')'
            hiCount += 1   // optimistic: treat as '('
        }

        if hiCount < 0 {
            return false   // even the most optimistic interpretation can't recover
        }
        loCount = max(loCount, 0)   // extra '*'s can always fall back to "empty" instead
    }

    return loCount == 0
}

// smoke test — same cases as the brute force
print(checkValidString("()"))     // true
print(checkValidString("(*)"))    // true
print(checkValidString("(*))"))   // true
print(checkValidString("(((")) // false

Big-O: O(n) time — a single left-to-right pass over s. O(1) extra space.

---

🔑 The Key Insight

The brute force explores every combination of * interpretations independently, even though most of them are redundant — many different interpretations of the *s seen so far produce the exact same open-paren count, so there's no need to track them as separate branches. The optimal version compresses "every possible open-paren count achievable so far" down to just its minimum and maximum, since every integer in between is also achievable (each * shifts the range by one in either direction, never skipping values) — so the range alone fully describes what's reachable. Clamping loCount at zero encodes "an excess pessimistic * can always be reinterpreted as empty instead," and returning false the moment hiCount goes negative encodes "even the most generous interpretation of every * so far can't produce a valid prefix" — both are safe because they only discard interpretations that could never possibly be needed for a valid final match.

---

🔗 Related Chapters

• Greedy — the running loCount/hiCount range is updated once per character and never revisited, the same single-pass running-state shape as Maximum Subarray's Kadane scan.
• Arrays and Strings — the string is walked left to right as a sequence of characters, the same traversal shape as every other greedy string-scan problem in this batch.
• DFS and Backtracking — the brute force's three-way branch on every * (try '(', try ')', try empty, backtrack) is the exact recursive-exploration shape this pattern covers.

---

🧸 Memory Sentence

Valid Parenthesis String is a min/max open-count range — every * stretches the range by one in both directions, clamp the low end at zero, and fail the instant the high end goes negative.

---

✅ Check Your Understanding

1. Why is it safe to clamp loCount at zero instead of letting it go negative like hiCount is allowed to (briefly, before returning false)?
2. Trace checkValidString("(*))") step by step, listing loCount and hiCount after each character. Why does the final loCount == 0 correctly report true?
3. Why does hiCount < 0 at any point guarantee the string is invalid, even though loCount might still be nonnegative at that same point?

---

⬅️ Previous: Partition Labels · Next: Insert Interval ➡️