Valid Parenthesis String

MEDIUM✓ CHIP-TIMEDLC #678 — FULL STATEMENT ↗

The drill: A string of '(', ')' and '*' where every '*' can freely stand in for '(', ')', or nothing at all. Decide whether some assignment of the wildcards makes the whole string balanced.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string mixes three characters: '(', ')', and '*'. Each '*' is a wildcard that can independently be treated as an open paren, a close paren, or nothing at all — an empty placeholder that vanishes from the string.

The task is deciding whether at least one way of resolving every wildcard turns the whole string into a properly balanced sequence of parentheses, where every open has a later matching close and nothing closes before it opens.

Different wildcards can be resolved differently from each other; the only requirement is that some single consistent assignment across all of them produces balance.

EX 01

s = "()"

→ true

ALREADY BALANCED, NO WILDCARDS

EX 02

s = "(*)"

→ true

STAR CAN BE EMPTY

EX 03

s = "(*"

→ true

STAR STANDS IN FOR THE MISSING CLOSE

the string contains only the characters '(', ')', and '*'
each '*' independently resolves to '(', ')', or an empty string
a valid resolution must keep every prefix from closing more than it opened
the verdict is whether any resolution at all achieves full balance

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Trying every wildcard assignment is exponential. What's the smallest summary of 'how many opens am I currently holding' that still lets you decide validity?

HINT 2 THE STRUCTURE

Instead of one open-count, track a whole range: the lowest and highest number of opens still reachable at this point, given every wildcard choice made so far.

HINT 3 ONE STEP FROM THE ANSWER

'(' shifts both ends of the range up, ')' shifts both down, '*' widens the range by one on each side. Clamp the low end at zero as you go; if the high end ever dips below zero, no assignment saves it. Balanced iff the range still contains zero at the end.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE OPEN-COUNT RANGEPATTERN · GREEDY — LO/HI RANGEs = "(*))"

(

)

OPEN RANGE [lo, hi]

lo → 0

hi → 0

STEP 1

s = "(*))". Each '*' can be '(', ')', or nothing — track the whole range of possible open-paren counts instead of one number.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/valid-parenthesis-string.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 17 LN

class Solution:
    def checkValidString(self, s: str) -> bool:
        def valid(i: int, open_count: int) -> bool:
            if open_count < 0:
                return False
            if i == len(s):
                return open_count == 0
            c = s[i]
            if c == "(":
                return valid(i + 1, open_count + 1)
            if c == ")":
                return valid(i + 1, open_count - 1)
            # '*' — try all three interpretations
            return (
                valid(i + 1, open_count + 1)
                or valid(i + 1, open_count - 1)
                or valid(i + 1, open_count)
            )

        return valid(0, 0)

TIME O(3^K)SPACE O(N)PYTHON · TRAINING PACE · 20 LN

class Solution {
    public boolean checkValidString(String s) {
        int lo = 0, hi = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                lo--;
                hi--;
            } else {
                lo--;
                hi++;
            }
            if (hi < 0) return false;
            lo = Math.max(lo, 0);
        }
        return lo == 0;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 20 LN

class Solution {
    public boolean checkValidString(String s) {
        return valid(s, 0, 0);
    }

    private boolean valid(String s, int i, int open) {
        if (open < 0) return false;
        if (i == s.length()) return open == 0;
        char c = s.charAt(i);
        if (c == '(') return valid(s, i + 1, open + 1);
        if (c == ')') return valid(s, i + 1, open - 1);
        return valid(s, i + 1, open + 1) || valid(s, i + 1, open - 1) || valid(s, i + 1, open);
    }
}

TIME O(3^K)SPACE O(N)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED