678. Valid Parenthesis String (Medium)

Problem

Given a string s containing only '(', ')', and '*', return true if s is a valid parenthesis string. '*' may represent '(', ')', or the empty string.

Example

s = "()" → true
s = "(*)" → true
s = "(*))" → true
s = "((" → false

LeetCode 678 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every `*` interpretation

Enumerate 3^(count of *) interpretations; test each as a plain parenthesis string. Exponential, skip past tiny inputs.

from itertools import product

def check_valid_string(s):
    star_positions = [i for i, ch in enumerate(s) if ch == '*']
    # Each star can be '(', ')', or '' (empty)
    for assignment in product('()_', repeat=len(star_positions)):       # L1: 3^k combos
        candidate = list(s)
        for pos, ch in zip(star_positions, assignment):
            candidate[pos] = '' if ch == '_' else ch
        # Validate as plain parens
        balance = 0
        ok = True
        for c in candidate:
            if not c: continue
            balance += 1 if c == '(' else -1
            if balance < 0: ok = False; break
        if ok and balance == 0:
            return True
    return False

function checkValidString(s: string): boolean {
    const stars = [...s].map((ch, i) => ch === '*' ? i : -1).filter(i => i >= 0);
    const k = stars.length;
    // Each star: 0 = '(', 1 = ')', 2 = empty
    for (let mask = 0; mask < 3 ** k; mask++) {           // L1: 3^k combos
        const arr = s.split('');
        let m = mask;
        for (const pos of stars) {
            const choice = m % 3;
            arr[pos] = choice === 0 ? '(' : choice === 1 ? ')' : '';
            m = Math.floor(m / 3);
        }
        let balance = 0;
        let ok = true;
        for (const c of arr) {
            if (!c) continue;
            balance += c === '(' ? 1 : -1;
            if (balance < 0) { ok = false; break; }
        }
        if (ok && balance === 0) return true;
    }
    return false;
}

func checkValidString(s string) bool {
    // collect star positions
    var stars []int
    for i, ch := range s {
        if ch == '*' { stars = append(stars, i) }
    }
    k := len(stars)
    total := 1
    for i := 0; i < k; i++ { total *= 3 }               // L1: 3^k combos
    runes := []rune(s)
    for mask := 0; mask < total; mask++ {
        arr := make([]rune, len(runes))
        copy(arr, runes)
        m := mask
        for _, pos := range stars {
            switch m % 3 {
            case 0: arr[pos] = '('
            case 1: arr[pos] = ')'
            case 2: arr[pos] = 0
            }
            m /= 3
        }
        balance, ok := 0, true
        for _, c := range arr {
            if c == 0 { continue }
            if c == '(' { balance++ } else { balance-- }
            if balance < 0 { ok = false; break }
        }
        if ok && balance == 0 { return true }
    }
    return false
}

final class Solution {
    func checkValidString(_ s: String) -> Bool {
        let characters = Array(s)
        func search(_ index: Int, _ open: Int) -> Bool {
            if open < 0 { return false }
            if index == characters.count { return open == 0 }
            if characters[index] == "(" { return search(index + 1, open + 1) }
            if characters[index] == ")" { return search(index + 1, open - 1) }
            return search(index + 1, open) || search(index + 1, open + 1) || search(index + 1, open - 1)
        }
        return search(0, 0)
    }
}

For each of the 3^k assignments to k stars, run a linear validation. Total $O(3^k · n)$ . The DP and two-pointer approaches below are dramatically better.

Complexity

Time: $O(3^k · n)$ , where k = number of *.
Space: $O(n)$ .

Approach 2: Top-down DP on (index, open_count)

State: position and currently unclosed ( count. Transitions depend on the character.

from functools import lru_cache

def check_valid_string(s):
    @lru_cache(maxsize=None)
    def f(i, opens):                            # L1: O(n²) unique states
        if opens < 0:
            return False                        # L2: prune negative opens
        if i == len(s):
            return opens == 0                   # L3: valid iff balanced
        if s[i] == '(':
            return f(i + 1, opens + 1)         # L4: O(1) per memoized call
        if s[i] == ')':
            return f(i + 1, opens - 1)         # L5: O(1)
        # '*': try all three interpretations
        return (f(i + 1, opens + 1)            # L6: treat as '('
                or f(i + 1, opens)             # L7: treat as empty
                or f(i + 1, opens - 1))        # L8: treat as ')'
    return f(0, 0)

function checkValidString(s: string): boolean {
    const memo = new Map<string, boolean>();
    function f(i: number, opens: number): boolean {     // L1: O(n²) unique states
        if (opens < 0) return false;                    // L2: prune negative opens
        if (i === s.length) return opens === 0;         // L3: valid iff balanced
        const key = `${i},${opens}`;
        if (memo.has(key)) return memo.get(key)!;
        let result: boolean;
        if (s[i] === '(') {
            result = f(i + 1, opens + 1);              // L4: O(1) per memoized call
        } else if (s[i] === ')') {
            result = f(i + 1, opens - 1);              // L5: O(1)
        } else {
            // '*': try all three interpretations
            result = f(i + 1, opens + 1)               // L6: treat as '('
                  || f(i + 1, opens)                   // L7: treat as empty
                  || f(i + 1, opens - 1);              // L8: treat as ')'
        }
        memo.set(key, result);
        return result;
    }
    return f(0, 0);
}

func checkValidString(s string) bool {
    memo := map[[2]int]bool{}
    visited := map[[2]int]bool{}
    var f func(i, opens int) bool
    f = func(i, opens int) bool {                        // L1: O(n²) unique states
        if opens < 0 { return false }                    // L2: prune negative opens
        if i == len(s) { return opens == 0 }             // L3: valid iff balanced
        key := [2]int{i, opens}
        if visited[key] { return memo[key] }
        var result bool
        if s[i] == '(' {
            result = f(i+1, opens+1)                    // L4: O(1) per memoized call
        } else if s[i] == ')' {
            result = f(i+1, opens-1)                    // L5: O(1)
        } else {
            result = f(i+1, opens+1) || f(i+1, opens) || f(i+1, opens-1) // L6-L8
        }
        memo[key] = result; visited[key] = true
        return result
    }
    return f(0, 0)
}

final class Solution {
    func checkValidString(_ s: String) -> Bool {
        let characters = Array(s)
        var memo: [Int: Bool] = [:]
        func search(_ index: Int, _ open: Int) -> Bool {
            if open < 0 { return false }
            if index == characters.count { return open == 0 }
            let key = index * (characters.count + 1) + open
            if let cached = memo[key] { return cached }
            let result: Bool
            if characters[index] == "(" { result = search(index + 1, open + 1) }
            else if characters[index] == ")" { result = search(index + 1, open - 1) }
            else { result = search(index + 1, open) || search(index + 1, open + 1) || search(index + 1, open - 1) }
            memo[key] = result
            return result
        }
        return search(0, 0)
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (unique states)	$O(1)$	n * n	$O(n²)$
L6-L8 (star branches)	$O(1)$ memoized	up to n²	$O(n²)$ ← dominates

There are $O(n²)$ distinct (i, opens) states; each is computed once due to memoization.

Complexity

Time: $O(n²)$ . States = n × n, each $O(1)$ .
Space: $O(n²)$ for the memo table.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Two-pointer range of possible open counts (optimal)

Track lo and hi, the minimum and maximum possible number of unclosed ( so far:

( → both lo and hi increase.
) → both decrease; clamp lo at 0.
* → lo can decrease (if * = )) and hi can increase (if * = ().

If hi < 0 at any point, there are unmatched ). At the end, 0 ∈ [lo, hi] means a valid interpretation exists.

def check_valid_string(s):
    lo = hi = 0                     # L1: O(1)
    for ch in s:                    # L2: single pass, n iterations
        if ch == '(':
            lo += 1                 # L3: O(1)
            hi += 1                 # L4: O(1)
        elif ch == ')':
            lo -= 1                 # L5: O(1)
            hi -= 1                 # L6: O(1)
        else:
            lo -= 1                 # L7: O(1), star acts as ')'
            hi += 1                 # L8: O(1), star acts as '('
        if hi < 0:                  # L9: too many unmatched ')'
            return False
        if lo < 0:
            lo = 0                  # L10: clamp, star already absorbed the deficit
    return lo == 0                  # L11: O(1)

function checkValidString(s: string): boolean {
    let lo = 0;                                            // L1: O(1)
    let hi = 0;
    for (const ch of s) {                                 // L2: single pass, n iterations
        if (ch === '(') {
            lo++;                                          // L3: O(1)
            hi++;                                          // L4: O(1)
        } else if (ch === ')') {
            lo--;                                          // L5: O(1)
            hi--;                                          // L6: O(1)
        } else {
            lo--;                                          // L7: O(1), star acts as ')'
            hi++;                                          // L8: O(1), star acts as '('
        }
        if (hi < 0) return false;                          // L9: too many unmatched ')'
        if (lo < 0) lo = 0;                               // L10: clamp
    }
    return lo === 0;                                       // L11: O(1)
}

func checkValidString(s string) bool {
    lo, hi := 0, 0                                         // L1: O(1)
    for _, ch := range s {                                 // L2: single pass, n iterations
        if ch == '(' {
            lo++; hi++                                     // L3, L4: O(1)
        } else if ch == ')' {
            lo--; hi--                                     // L5, L6: O(1)
        } else {
            lo--; hi++                                     // L7, L8: O(1)
        }
        if hi < 0 { return false }                         // L9: too many unmatched ')'
        if lo < 0 { lo = 0 }                              // L10: clamp
    }
    return lo == 0                                         // L11: O(1)
}

final class Solution {
    func checkValidString(_ s: String) -> Bool {
        var low = 0, high = 0
        for character in s {
            if character == "(" { low += 1; high += 1 }
            else if character == ")" { low = max(0, low - 1); high -= 1 }
            else { low = max(0, low - 1); high += 1 }
            if high < 0 { return false }
        }
        return low == 0
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2-L10 (scan)	$O(1)$	n	$O(n)$ ← dominates
L11 (final check)	$O(1)$	1	$O(1)$

A single pass over the string; all operations per character are $O(1)$ .

Complexity

Time: $O(n)$ , driven by L2/L3-L10 (single linear scan).
Space: $O(1)$ .

Two-stack alternative

Push positions of ( onto one stack and positions of * onto another; when you see ), pop from ( first, else from *. At the end, ensure remaining ( positions each have a later *. Same $O(n)$ , more bookkeeping.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Enumerate interpretations	3^k	$O(k)$
DP on (i, opens)	$O(n²)$	$O(n²)$
Range of possible opens	$O(n)$	$O(1)$

The [lo, hi] range trick is the right answer; * expands the range, ( and ) shift it.

Test cases

func checkValidString(s string) bool {
    lo, hi := 0, 0
    for _, ch := range s {
        if ch == '(' { lo++; hi++ } else if ch == ')' { lo--; hi-- } else { lo--; hi++ }
        if hi < 0 { return false }
        if lo < 0 { lo = 0 }
    }
    return lo == 0
}

# Quick smoke tests, paste into a REPL or save as test_678.py and run.
# Uses the canonical implementation (Approach 3: range of possible opens).

def check_valid_string(s):
    lo = 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
        if lo < 0:
            lo = 0
    return lo == 0

def _run_tests():
    assert check_valid_string("()") == True
    assert check_valid_string("(*)") == True
    assert check_valid_string("(*))") == True
    assert check_valid_string("((") == False
    assert check_valid_string("*") == True        # star acts as empty
    assert check_valid_string("(*") == True       # star closes the open paren
    assert check_valid_string(")") == False       # unmatched close
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function checkValidString(s: string): boolean {
    let lo = 0;
    let hi = 0;
    for (const ch of s) {
        if (ch === '(') { lo++; hi++; }
        else if (ch === ')') { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;
        if (lo < 0) lo = 0;
    }
    return lo === 0;
}

console.assert(checkValidString('()') === true);
console.assert(checkValidString('(*)') === true);
console.assert(checkValidString('(*))') === true);
console.assert(checkValidString('((') === false);
console.assert(checkValidString('*') === true);        // star acts as empty
console.assert(checkValidString('(*') === true);       // star closes the open paren
console.assert(checkValidString(')') === false);       // unmatched close
console.log("all tests pass");

Strings, input
Stacks, two-stack alternative

Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.
Stack Parsing, the last open, first closed model for nested syntax and reversible operations.

678. Valid Parenthesis String (Medium)

Problem

Try it yourself

Approach 1: Brute force, try every * interpretation

Approach 2: Top-down DP on (index, open_count)

Approach 3: Two-pointer range of possible open counts (optimal)

Two-stack alternative

Summary

Test cases

Related data structures

Related concepts

Approach 1: Brute force, try every `*` interpretation