129.Valid Parenthesis String

MediumGreedy · 8/8

Problem

Given a string s containing only '(', ')' and '*', return true if it can be a valid parentheses string.

'*' is a wildcard: it may be treated as '(', as ')', or as an empty string. A string is valid when every '(' has a matching ')' that comes after it, and every ')' has a matching '(' before it.

Examples

Input:  s = "()"
Output: true

Input:  s = "(*)"
Output: true
Explanation: Treat '*' as empty.

Input:  s = "(*))"
Output: true
Explanation: Treat '*' as '(' -> "(())".

Input:  s = "*("
Output: false
Explanation: The '(' has nothing after it to close it.

Constraints

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

💡 Key Insight

Without wildcards, we would track a single open count. With wildcards, the count is no longer one number but a range of possibilities [lo, hi]: lo assumes every * closes (or vanishes when nothing is open), hi assumes every * opens. If hi ever drops below 0, there are too many ')' no matter what; clamp lo at 0 because we may choose a * to be empty instead. The string is valid iff lo == 0 at the end — some choice of wildcards closes everything.

Brute Force Recursion

TimeO(3^n)SpaceO(n)

Intuition

Try all three interpretations of each * while tracking the number of unmatched '('. A branch dies if the count goes negative. At the end of the string the branch succeeds only with open == 0.

Algorithm

check(i, open): if open < 0 return false; if i == n return open == 0.
'(' → check(i + 1, open + 1); ')' → check(i + 1, open - 1).
'*' → any of check(i + 1, open + 1), check(i + 1, open - 1), check(i + 1, open).

Visualization

s = "(*)"
check(0,0) '(' -> check(1,1)
check(1,1) '*' -> as '(' check(2,2) -> ')' -> check(3,1) false
               -> as ')' check(2,0) -> ')' -> check(3,-1) false
               -> empty  check(2,1) -> ')' -> check(3,0) true

Code

java

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

    private boolean check(String s, int i, int open) {
        if (open < 0) {
            return false; // a ')' with nothing to match
        }
        if (i == s.length()) {
            return open == 0;
        }
        char c = s.charAt(i);
        if (c == '(') {
            return check(s, i + 1, open + 1);
        }
        if (c == ')') {
            return check(s, i + 1, open - 1);
        }
        // '*' : try '(', ')' and empty
        return check(s, i + 1, open + 1)
            || check(s, i + 1, open - 1)
            || check(s, i + 1, open);
    }
}

Complexity

Time: O(3^n) — three branches per wildcard.
Space: O(n) — recursion depth.

Memoized DP

TimeO(n²)SpaceO(n²)

Intuition

The recursion's state is fully described by (i, open), and open can never exceed n. So there are only O(n²) distinct states; caching each result removes the exponential blow-up.

Algorithm

memo[i][open] stores null / true / false.
Same transitions as the brute force, but return the cached result if present and store it before returning.
Prune: if open > n - i, the remaining characters cannot close everything — return false.

Visualization

state (i, open)	char	result
(3, 0)	end	true
(2, 1)	`)`	(3,0) = true
(1, 1)	`*`	(2,2) false, (2,0) false, (2,1) true → true
(0, 0)	`(`	(1,1) = true

s = "(*)" → true.

Code

java

class Solution {
    private Boolean[][] memo;

    public boolean checkValidString(String s) {
        int n = s.length();
        memo = new Boolean[n + 1][n + 2];
        return check(s, 0, 0);
    }

    private boolean check(String s, int i, int open) {
        if (open < 0 || open > s.length() - i) {
            return false; // negative, or too many opens left to close
        }
        if (i == s.length()) {
            return open == 0;
        }
        if (memo[i][open] != null) {
            return memo[i][open];
        }
        char c = s.charAt(i);
        boolean result;
        if (c == '(') {
            result = check(s, i + 1, open + 1);
        } else if (c == ')') {
            result = check(s, i + 1, open - 1);
        } else {
            result = check(s, i + 1, open + 1)
                || check(s, i + 1, open - 1)
                || check(s, i + 1, open);
        }
        memo[i][open] = result;
        return result;
    }
}

Complexity

Time: O(n²) — n · n states, each O(1).
Space: O(n²) — the memo table.

Two Stacks

TimeO(n)SpaceO(n)

Intuition

Push the indices of '(' and '*' onto two stacks. On ')', prefer to match a real '('; otherwise spend a '*'; if neither exists, fail. At the end, leftover '(' must each be closed by a '*' that appears after it — so pop pairs and check that the star's index is larger.

Algorithm

For each index i: '(' → push to open; '*' → push to star; ')' → pop open if non-empty, else pop star, else return false.
While both stacks are non-empty: if open.peek() > star.peek() return false; else pop both.
Return open.isEmpty().

Visualization

s = "*("          open=[1]  star=[0]
end: open top 1 > star top 0 -> the '*' is before the '(' -> false

s = "(*))"
i=0 '(' open=[0]
i=1 '*' star=[1]
i=2 ')' pop open      open=[]
i=3 ')' pop star      star=[]
open empty -> true

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean checkValidString(String s) {
        Deque<Integer> open = new ArrayDeque<>();
        Deque<Integer> star = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                open.push(i);
            } else if (c == '*') {
                star.push(i);
            } else if (!open.isEmpty()) {
                open.pop(); // prefer a real '('
            } else if (!star.isEmpty()) {
                star.pop(); // use '*' as '('
            } else {
                return false;
            }
        }
        // close remaining '(' with a '*' that comes after it
        while (!open.isEmpty() && !star.isEmpty()) {
            if (open.pop() > star.pop()) {
                return false;
            }
        }
        return open.isEmpty();
    }
}

Complexity

Time: O(n) — each index is pushed and popped at most once.
Space: O(n) — the two stacks.

Greedy Range of Open CountsOptimal

TimeO(n)SpaceO(1)

Intuition

Track the minimum and maximum possible number of unmatched '(' after each character. '(' raises both; ')' lowers both; '*' lowers lo (treat as ')') and raises hi (treat as '('). If hi < 0, even treating every star as '(' cannot save us. lo is clamped at 0 because a negative minimum just means we would choose some star to be empty instead. Every value between lo and hi is achievable, so the answer is whether 0 is in the final range, i.e. lo == 0.

Algorithm

lo = 0, hi = 0.
For each char: '(' → lo++, hi++; ')' → lo--, hi--; '*' → lo--, hi++.
If hi < 0 return false. Set lo = max(lo, 0).
Return lo == 0.

Dry Run

flowchart LR
    A["start<br/>lo 0, hi 0"] -->|"'('"| B["lo 1, hi 1"]
    B -->|"'*'"| C["lo 0, hi 2"]
    C -->|"')'"| D["lo -1 -> 0, hi 1"]
    D -->|"')'"| E["lo -1 -> 0, hi 0"]
    E --> F{"lo == 0?"}
    F -->|"yes"| G["return true"]

s = "*("
'*' : lo = -1 -> 0, hi = 1
'(' : lo = 1,       hi = 2
end: lo = 1 != 0 -> false

Code

java

class Solution {
    public boolean checkValidString(String s) {
        int lo = 0; // fewest unmatched '(' possible
        int hi = 0; // most unmatched '(' possible
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                lo--;
                hi--;
            } else { // '*'
                lo--;
                hi++;
            }
            if (hi < 0) {
                return false; // too many ')' even if every '*' opens
            }
            lo = Math.max(lo, 0); // can't have negative open count
        }
        return lo == 0;
    }
}

Complexity

Time: O(n) — single pass.
Space: O(1) — two counters.

Complexity Comparison

Approach	Time	Space
Brute Force Recursion	O(3^n)	O(n)
Memoized DP	O(n²)	O(n²)
Two Stacks	O(n)	O(n)
Greedy Range of Open Counts	O(n)	O(1)

Common Pitfalls

Counting stars as a pool without considering position — "*(" has one star and one '(' but is invalid.
Returning hi == 0 or lo == 0 && hi == 0 at the end; the correct test is lo == 0.
Forgetting to clamp lo at 0, which lets a negative minimum hide a valid configuration.
In the two-stack approach, preferring a '*' over a real '(' when closing — that wastes flexible characters.