#678 Valid Parenthesis String

frequently reported atByteDance / TikTok Amazon Meta Google

the problem

In plain words

A string s has only three kinds of characters: '(', ')' and ''. Each '' can stand for '(' or ')' or nothing at all. Return true if some choice for the stars makes s balanced: every '(' is closed by a later ')', and no ')' comes without an open '(' before it.

in s = "()"

out true

in s = "(*)"

out true

The star is nothing.

in s = "(*))"

out true

The star is '(': "(())".

in s = "("

out false

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGreedy choice Stack for matching & nesting

You don't have to decide what each star is. Track the range of possible open counts: lo (the fewest '(' that could be open) and hi (the most). The string is valid if 0 is still possible at the end.

solutions

From brute force to optimal

Walk the string with a counter of open '('. A star branches three ways.

'(' → open + 1; ')' → open − 1; '*' → try all three.
Fail as soon as open < 0.
Succeed if open == 0 at the end.

timeO(n · 3ᵏ)

Each of the k stars triples the number of paths, and a path walks up to n characters. 100 stars is hopeless.

spaceO(n)

The recursion is one frame per character.

javajava.util.*

1class Solution {2    public boolean checkValidString(String s) {3        return tryAll(s, 0, 0);4    }5 6    /** open = how many '(' are still waiting for a ')'. Each '*' tries all three meanings. */7    private boolean tryAll(String s, int i, int open) {8        if (open < 0) return false;                    // a ')' with nothing to close9        if (i == s.length()) return open == 0;10        char c = s.charAt(i);11        if (c == '(') return tryAll(s, i + 1, open + 1);12        if (c == ')') return tryAll(s, i + 1, open - 1);13        return tryAll(s, i + 1, open + 1)              // '*' as '('14            || tryAll(s, i + 1, open - 1)              // '*' as ')'15            || tryAll(s, i + 1, open);                 // '*' as nothing16    }17}

The answer from position i depends only on i and how many '(' are open. Cache it.

can(i, open) follows the same rules as the brute force.
Store each result in memo[i][open] (open never exceeds n).
Return can(0, 0).

timeO(n²)

n × (n + 1) states, each solved once with O(1) work.

spaceO(n²)

The memo table, plus O(n) recursion depth.

javajava.util.*

1class Solution {2    public boolean checkValidString(String s) {3        int n = s.length();4        Boolean[][] memo = new Boolean[n + 1][n + 1];  // memo[i][open]; open never exceeds n5        return can(s, 0, 0, memo);6    }7 8    private boolean can(String s, int i, int open, Boolean[][] memo) {9        if (open < 0) return false;10        if (i == s.length()) return open == 0;11        if (memo[i][open] != null) return memo[i][open];12        char c = s.charAt(i);13        boolean ok;14        if (c == '(') ok = can(s, i + 1, open + 1, memo);15        else if (c == ')') ok = can(s, i + 1, open - 1, memo);16        else ok = can(s, i + 1, open + 1, memo) || can(s, i + 1, open - 1, memo) || can(s, i + 1, open, memo);17        memo[i][open] = ok;18        return ok;19    }20}

Match each ')' with the latest '(' first, else with a star. At the end, pair each leftover '(' with a star that comes after it.

Push the indices of '(' and '*' on two stacks.
On ')': pop a '(' if any, else a '*', else fail.
While '(' remain: pop one '(' and one '*'; the star's index must be larger.

timeO(n)

Each index is pushed and popped at most once.

spaceO(n)

Two stacks of indices.

javajava.util.*

1class Solution {2    public boolean checkValidString(String s) {3        Deque<Integer> opens = new ArrayDeque<>(), stars = new ArrayDeque<>(); // indices4        for (int i = 0; i < s.length(); i++) {5            char c = s.charAt(i);6            if (c == '(') opens.push(i);7            else if (c == '*') stars.push(i);8            else if (!opens.isEmpty()) opens.pop();    // a real '(' closes it first9            else if (!stars.isEmpty()) stars.pop();    // otherwise a '*' plays '('10            else return false;11        }12        while (!opens.isEmpty()) {                     // leftover '(' need a '*' AFTER them13            if (stars.isEmpty() || stars.pop() < opens.pop()) return false;14        }15        return true;16    }17}

Keep the smallest and largest number of '(' that could be open. A star widens the range by one each way.

lo = hi = 0.
'(' → lo++, hi++; ')' → lo--, hi--; '*' → lo--, hi++.
If hi < 0, return false. Clamp lo = max(lo, 0).
At the end, return lo == 0.

timeO(n)

One pass, O(1) work per character.

spaceO(1)

Two integers.

javajava.util.*

1class Solution {2    public boolean checkValidString(String s) {3        int lo = 0, hi = 0; // fewest and most '(' that could still be open4        for (char c : s.toCharArray()) {5            if (c == '(') {6                lo++;7                hi++;8            } else if (c == ')') {9                lo--;10                hi--;11            } else { // '*': ')' lowers lo, '(' raises hi12                lo--;13                hi++;14            }15            if (hi < 0) return false; // too many ')' even if every '*' is '('16            lo = Math.max(lo, 0); // a count below 0 is never a real choice17        }18        return lo == 0; // some choice closes every '('19    }20}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public boolean checkValidString(String s) {3        int lo = 0, hi = 0; // fewest and most '(' that could still be open4        for (char c : s.toCharArray()) {5            if (c == '(') {6                lo++;7                hi++;8            } else if (c == ')') {9                lo--;10                hi--;11            } else { // '*': ')' lowers lo, '(' raises hi12                lo--;13                hi++;14            }15            if (hi < 0) return false; // too many ')' even if every '*' is '('16            lo = Math.max(lo, 0); // a count below 0 is never a real choice17        }18        return lo == 0; // some choice closes every '('19    }20}

in the room

How to say it in the interview

talk track

Start from Valid Parentheses (LC 20): one counter of open brackets is enough. The stars make that counter uncertain.
Say: "Instead of guessing, I'll track the range of possible counts, lo and hi."
Explain the two checks: hi < 0 means too many ')' even in the best case; lo is clamped because a negative count is never a real path.
Mention the memo DP as the safe fallback: O(n²) with n ≤ 100 is fine too.

traps

Skipping the clamp: on "*()" lo ends at −1, and lo == 0 wrongly says false.
Dropping the hi < 0 check: on ")(*" the counts recover and the end check wrongly says true. A ')' with nothing open can never be fixed later.
Two stacks: pairing a leftover '(' with a star that comes before it. "*(" is not valid.

what they ask next

Follow-ups

Return one valid assignment of the stars?

Use the two-stack method: it decides each star's role while matching. Unused stars become empty.

Several bracket types like ()[]{} with wildcards?

One counter can't tell the types apart, so the range trick breaks. Fall back to a DP over substrings (is s[i..j] valid?), O(n³).

before you submit

Edge cases to test

"*" → true: the star is empty.
"**(" → false: stars before a '(' can't close it.
")(*" → false: a ')' with nothing open is fatal at once.
50 '(' then 50 '*' → true: every star closes one. Plain recursion would explode here.

practise next