Valid Parenthesis String

1. Problem & Core Objective

A string contains '(', ')' and '*'. Each '*' may be treated as '(', ')', or the empty string. Return whether the string can be made valid.

s = "()"      →  true
s = "(*)"     →  true    (* = empty, or "(" ")" balanced differently)
s = "(*))"    →  true    (* = "(")
s = ")("      →  false
s = "(*("     →  false

Constraints: 1 <= s.length <= 100, characters are '(', ')', '*'

What's actually being tested: whether you can avoid branching on uncertainty. Committing each * to one of three meanings gives 3^n cases. The insight is that the reachable open-paren counts always form a contiguous interval, so two integers replace the entire set of possibilities.

2. First-Principles Thought Process

Start from validity without wildcards

Without *, validity is a one-pass counter: increment on (, decrement on ), fail if it ever goes negative, and require 0 at the end. The counter is "how many open brackets are currently unmatched".

The wildcard makes the count a set

With *, after reading a prefix there isn't one open-count — there's a set of counts, one per interpretation of the stars so far. "(*" admits open counts {0, 1, 2}.

Tracking that set is O(n) states, which is already fine at n = 100. But there's a better observation.

The set is always an interval

Reading one more character maps every element of the set as follows:

( and ) shift the whole set by a constant — an interval stays an interval. * replaces {x} by {x−1, x, x+1}, so an interval [lo, hi] becomes [lo−1, hi+1], again contiguous and with no holes.

Starting from {0}, the set is therefore always a contiguous interval, and [lo, hi] describes it exactly.

The two guards, which are not symmetric

hi < 0 → return false. hi is the most optimistic count — every * read as (. If even that is negative, there are genuinely more closers than anything could match. The string is dead.

lo < 0 → clamp to 0, don't fail. A negative minimum isn't a state; it's an interpretation that already died. Choosing ) for a * when nothing is open isn't a legal move you took, it's one that was never available. Clamping keeps lo meaning "the fewest open brackets among surviving interpretations".

Measured: without the clamp, "(*)" returns false instead of true. The trace is ( → [1,1], * → [0,2], ) → [−1,1], and the final lo == 0 test fails on a −1 that should have been 0.

The final test

return lo == 0. Zero open brackets must be achievable, and since the set is the interval [lo, hi] with lo >= 0 after clamping, 0 is in it exactly when lo == 0.

Testing hi == 0 would demand that every interpretation ends balanced, which is far too strong.

Why this counts as greedy

Nothing is chosen — the algorithm computes the exact reachable set and reads the answer off it. Like Jump Game, the "greedy" label comes from the shape (one pass, O(1) state, no backtracking) rather than from a choice needing justification. The proof obligation is contiguity, not optimality.

3. Solution Paths

Approach 1 — Brute force, try all three meanings

public boolean checkValidString(String s) {
    return dfs(s, 0, 0, new HashMap<>());
}

private boolean dfs(String s, int i, int open, Map<Integer,Boolean> memo) {
    if (open < 0) return false;
    if (i == s.length()) return open == 0;
    int key = i * 200 + open;                              // n <= 100, so open <= 100
    Boolean cached = memo.get(key);
    if (cached != null) return cached;

    char c = s.charAt(i);
    boolean res;
    if (c == '(')      res = dfs(s, i + 1, open + 1, memo);
    else if (c == ')') res = dfs(s, i + 1, open - 1, memo);
    else res = dfs(s, i + 1, open + 1, memo)               // '*' as '('
            || dfs(s, i + 1, open,     memo)               // '*' as ''
            || dfs(s, i + 1, open - 1, memo);              // '*' as ')'

    memo.put(key, res);
    return res;
}

• Time O(n²) with the memo, O(3^n) without · Space O(n²)

This is the reference the optimal solution was checked against.

Counter-questions on this approach

⭐ "Why is (i, open) a sufficient state?"

Because the future depends only on how many brackets are currently unmatched and where you are in the string — not on which particular stars produced that count. Two different star assignments reaching (i, open) are interchangeable from there on.

Recognising that the identity of the choices is irrelevant, only their aggregate, is what makes memoisation possible — and it's the same recognition that leads to the interval solution.

"i * 200 + open — why 200?"

It's a flat encoding of a 2-D key into an int, and the multiplier must exceed the range of open. With n <= 100, open is in [0, 100], so 200 is safely above it.

A boolean[n+1][n+1] with a separate visited array would be cleaner and avoid the magic number; I'd use that in production code. The encoded key is compact for a whiteboard.

"What makes this O(n²) rather than O(n)?"

The number of distinct states: n positions times n+1 possible open counts. Each is computed once and costs O(1), so O(n²) overall.

The interval solution is O(n) because it represents that entire column of open values as two numbers.

Approach 2 — Two stacks of indices

public boolean checkValidString(String s) {
    Deque<Integer> open = new ArrayDeque<>(), 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 matching a real '('
            else if (!star.isEmpty()) star.pop();          // otherwise spend a '*'
            else return false;
        }
    }
    while (!open.isEmpty() && !star.isEmpty())
        if (open.pop() > star.pop()) return false;         // a '*' that sits LEFT of its '(' is useless
    return open.isEmpty();
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why must the stacks hold indices rather than counts?"

The final loop needs to know whether each leftover * occurs after the ( it would close. A * to the left of an unmatched ( can't help — *( can never be balanced by reading the star as ).

The witness is "*(". By counts alone there is one ( and one *, which looks balanceable; by position the star sits to the left of the bracket it would have to close, so it cannot help. The answer is false, and only the index comparison catches it.

⭐ "Why prefer popping open over star when a ) arrives?"

Because a * is strictly more flexible — it can still serve as a closer later, or as nothing. Spending the rigid resource first and keeping the flexible one is the exchange argument here: any solution that spends a * while a ( was available can be rewritten to spend the ( instead, with no loss.

"Does this actually agree with the interval method?"

Yes — verified on 6,000 random strings over (, ), *, both checked against the exhaustive 3^n expansion. They agree everywhere.

"When would you write this one?"

If asked to identify which stars play which role, since the stacks retain positions. For a pure boolean the interval version is shorter and O(1) space.

Approach 3 — Interval of possible open counts (optimal)

public boolean checkValidString(String s) {
    int lo = 0, hi = 0;                       // fewest / most open brackets still possible
    for (char c : s.toCharArray()) {
        if (c == '(')      { lo++; hi++; }
        else if (c == ')') { lo--; hi--; }
        else               { lo--; hi++; }    // '*' → ')', '', or '('

        if (hi < 0) return false;             // too many closers even in the best case
        if (lo < 0) lo = 0;                   // a dead branch, not a state
    }
    return lo == 0;                           // zero must be ACHIEVABLE
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why can the set of possible open counts be summarised by just its endpoints?"

Because it's always contiguous. ( and ) translate the whole set by ±1, which preserves contiguity. * maps each x to {x−1, x, x+1}, so an interval [lo, hi] becomes [lo−1, hi+1] — still an interval with no gaps, because neighbouring elements' images overlap.

Starting from the single point {0}, contiguity is preserved at every step by induction. So two integers carry the same information as the full set.

⭐ "Why is hi < 0 fatal but lo < 0 not?"

They quantify differently. hi < 0 means every interpretation has more closers than openers — universal failure, nothing can recover. lo < 0 means some interpretation went negative, but others are still alive, so the string isn't dead.

Clamping lo to 0 prunes exactly the dead branches while leaving lo meaning "the fewest open brackets among surviving interpretations".

⭐ "What breaks without the clamp?"

lo drifts below the real minimum and the final lo == 0 test fails on strings that are valid. Measured: "(*)" returns false instead of true.

The trace makes it obvious — ( → [1,1], * → [0,2], ) → [−1,1]. The true set at the end is {0, 1}; without clamping the code believes it's {−1, 0, 1} and reports the minimum as −1.

"Why lo == 0 and not lo <= 0 or hi == 0?"

After clamping, lo >= 0 always, so lo <= 0 and lo == 0 are the same test — I'd write == because it states the requirement.

hi == 0 would be wrong in the other direction: it demands that every interpretation ends balanced. "(*)" ends with [0, 1] — reading the star as ( leaves one bracket open — yet the string is valid, because reading it as the empty string balances. Only the achievability of 0 matters, never its inevitability.

"Is a symmetric two-pass version equivalent?"

Scanning left to right treating * as (, then right to left treating * as ), and requiring both to stay non-negative — yes, that's a known equivalent formulation. It's two passes instead of one and I find the interval easier to justify, but it's a legitimate alternative worth naming if the interviewer asks for another angle.

4. Why the Optimal Solution Wins

O(n) is a lower bound, and O(1) space can't be improved.

Write the interval version. It is the shortest, it needs no auxiliary structure, and its correctness rests on a single provable claim — contiguity — rather than on a case analysis of what each * becomes.

5. Java Prerequisites

Character comparison

for (char c : s.toCharArray()) { if (c == '(') ... }

char is a primitive, so == compares values. toCharArray() copies once — s.charAt(i) in an indexed loop avoids the copy and is equally readable.

Clamping idiom

lo = Math.max(lo, 0);      // or: if (lo < 0) lo = 0;

ArrayDeque as a stack

Deque<Integer> st = new ArrayDeque<>();
st.push(i);    // addFirst
st.pop();      // removeFirst
st.peek();     // peekFirst

Prefer it to java.util.Stack, which is synchronised and iterates bottom-to-top — a genuine surprise if you ever print it (02).

Encoding a 2-D key into one int

int key = i * 200 + open;         // multiplier must exceed the second field's range

Compact, and a common source of collisions when the multiplier is chosen too small.

Autoboxing in Map<Integer,Boolean>

Boolean cached = memo.get(key);
if (cached != null) return cached;    // unboxes safely only after the null check

6. Interview Communication Guide

Clarifying questions: Can * be the empty string as well as a bracket (yes — three meanings, not two)? Is the empty string valid (yes, though the constraints say length ≥ 1)? Only round brackets (yes — multiple bracket types would change the approach completely)? What's the length bound (100, so even O(n²) is comfortable — but I'll aim for O(n))?

The pitch

"Without the wildcards this is a counter: +1 on (, −1 on ), fail if it goes negative, require 0 at the end.

With * there isn't one count any more — after each prefix there's a set of possible open counts, one per interpretation of the stars so far. Committing to each star gives 3^n branches, so I want to avoid choosing.

The useful observation is that this set is always a contiguous interval. ( and ) shift the whole set by one, which preserves contiguity, and a * turns each value x into {x−1, x, x+1} — so [lo, hi] becomes [lo−1, hi+1], still with no gaps. Starting from {0}, it's an interval forever. So two integers hold the whole set.

Then there are two guards, and they're deliberately asymmetric. If hi goes negative, every interpretation has too many closers — that's fatal, return false. If lo goes negative, only some interpretation died; others are alive, so I clamp lo to 0. A negative minimum isn't a state, it's a branch that was never legal.

At the end I check lo == 0 — zero open brackets must be achievable. Checking hi == 0 would wrongly demand that every interpretation balances.

O(n) time, O(1) space. The clamp is the line that breaks it if omitted: without it, "(*)" returns false instead of true."

Edge cases to volunteer:

Name "(*)" and "*(". The first is the clamp; the second is the input that defeats any solution that merely counts stars and brackets without regard to position.

7. Follow-Up Questions — Modified Constraints

⭐ "What if * could only be ( or ), never empty?"

The * step becomes {x−1, x+1} instead of {x−1, x, x+1} — which is not contiguous. It's an interval with alternating parity, so the whole argument collapses and the interval method silently breaks.

The fix is to track [lo, hi] plus the parity of the count, since every step now changes it by exactly 1. A string of odd length becomes automatically invalid. This is my favourite follow-up here because it targets exactly the property being exploited.

⭐ "Return one concrete valid assignment of the stars, not just a boolean."

The interval version discards that information. Use the two-stack approach, which retains positions: after the forward pass, the stars popped against ) are closers, the stars left over pair with unmatched ( from the right, and the rest are empty.

Alternatively reconstruct from the memoised DFS by walking the winning branch. Both are O(n) extra space — the price of a witness rather than a decision.

"What if there were multiple bracket types — (), [], {} — with wildcards?"

A single counter no longer suffices; you need a stack to enforce nesting order. With wildcards the stack contents become uncertain, so the state is a set of stacks rather than a set of counts — exponential, and the interval trick has no analogue.

Without wildcards it's plain stack matching (09). The wildcards are what make the single bracket type essential.

"What if the string were 10^6 long?"

The interval version is already O(n)/O(1), so nothing changes — I'd only switch toCharArray() to charAt to avoid the extra 10^6-byte copy. The memoised DFS would need 10^12 states and is out entirely.

"What's the minimum number of characters to insert to make it valid, allowing * to stay flexible?"

Different question. The classic version without * tracks unmatched openers and closers in one pass. With * you'd want the interval formulation extended to track the minimum insertions alongside — reachable, but it stops being a pure feasibility check and becomes an optimisation.

"What if * could expand to an arbitrary balanced string?"

Then * contributes 0 to the open count always — it's just a no-op for balance purposes, since any balanced string nets to zero. Delete all the stars and run the plain counter. Strictly easier than the original.

"Can you count how many valid assignments exist?"

Counting needs the full distribution over open counts, not just its endpoints — so back to a DP over (i, open), O(n²) time and space, summing instead of OR-ing. That's the standard signal that an existence check and a counting check are different problems even when they share a state space.