Difficulty: MediumGreedy

Valid Parenthesis String

Problem in Plain English

You are given a string of opening brackets, closing brackets and stars, where each star may act as an opening bracket, a closing bracket, or nothing at all. Return whether some choice for every star makes the whole bracket sequence balanced.

Problem Statement

Given a string s containing only (, ) and *, determine whether s can be a valid parenthesis string, where each * may be treated as (, as ), or as an empty string.

A string is valid when every ( is closed by a later ) with correct nesting. Return true if some assignment of all stars achieves this, otherwise return false.

Constraints

The string length is between 1 and 100 inclusive.
Each character is (, ), or *.

Examples

Example 1

Input: s = "(*))"
Output: true

Assign the star to an opening bracket. The resulting (()) has prefix balances 1, 2, 1, 0, all nonnegative and ending at zero.

Example 2

Input: s = "()"
Output: true

The opening bracket at index 0 is closed at index 1. No wildcard choice is needed, and the final balance is zero.

Example 3

Input: s = "(*)"
Output: true

The star must be empty: assigning either bracket leaves a length-three sequence that cannot balance. Removing it leaves ().

Example 4

Input: s = "*"
Output: true

At the minimum input length, the only successful choice is an empty star, producing the valid empty sequence.

Example 5

Input: s = "*("
Output: false

The final opening bracket has no later character that can close it. An earlier star cannot serve as a closing bracket for a later opening bracket.

Example 6

Input: s = ")*"
Output: false

The first character closes a bracket before any opening is available. No assignment to a later star can repair that invalid prefix.

Intuition

A balanced sequence never closes more brackets than it has opened, and finishes with no unmatched opens. A star can change that running balance by +1, -1, or 0. For Example 1, "(*))", using the star as an opening bracket gives "(())". Instead of committing to one interpretation too soon, keep every feasible prefix balance, then ask whether zero remains feasible at the end.

Approaches

Memoized Recursion

Solution Details

Reveal Memoized Recursion: intuition, complexity, and code

Intuition

Search states consist of the next index and the number of unmatched opening brackets. A star branches into all three permitted interpretations; ordinary brackets force one transition. Different assignments can reach the same state, and their remaining possibilities are identical, so caching that state avoids repeating its suffix search.

Step-by-Step Logic

Allocate a memo table indexed by position and unmatched-open count, then begin at dfs(0, 0). Example 1 starts with no unmatched brackets.
Reject a negative open count before any table access: that prefix has already closed too many brackets. At the end of the string, return whether open is zero.
For an uncached state, advance one position. An opening adds one unmatched open; a closing subtracts one. Example 1 begins with dfs(0, 0) moving to dfs(1, 1).
For a star, try opening, closing, then empty, stopping as soon as a child succeeds. In Example 1 the opening choice moves to dfs(2, 2); the closing and empty alternatives are skipped after success.
Cache each nonterminal state result while returning up the call stack. Example 1 closes twice, reaching dfs(4, 0), so true propagates to the initial call.

Why It Works

Define dfs(i, open) to mean that some assignment to the suffix starting at i completes the already valid prefix with open unmatched opening brackets. Negative open counts reject exactly the prefixes with a premature closing bracket. At the end, success requires zero unmatched opens. A fixed bracket has its single required transition; a star tries opening, closing, and empty, so the OR covers every allowed assignment and accepts only a valid one. By induction on the remaining suffix length, each state returns the correct answer. Since the suffix and unmatched count fully determine future choices, memoization preserves this result.

Dry Run

Memoized Recursion: variable states at each step
Event	State / character	Transition or result	Memo change
Enter	dfs(0, 0), `(`	call dfs(1, 1)	none
Enter	dfs(1, 1), `*`	opening choice calls dfs(2, 2)	none
Enter	dfs(2, 2), `)`	call dfs(3, 1)	none
Enter	dfs(3, 1), `)`	call dfs(4, 0)	none
Base case	dfs(4, 0), end	zero unmatched opens: true	terminal states are not cached
Return	dfs(3, 1)	true	memo[3][1] = true
Return	dfs(2, 2)	true	memo[2][2] = true
Return	dfs(1, 1)	first star branch succeeded; skip two others	memo[1][1] = true
Return	dfs(0, 0)	return true	memo[0][0] = true

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n^2)

Let n be the string length. At index i, open is at most i; therefore only O(n²) index/count pairs can be visited, with at most three constant-time transitions each. All three snippets eagerly allocate n rows of n + 1 memo entries, taking O(n²) time and space even when the search succeeds early. Recursion adds O(n) stack frames, dominated by the table; n is at most 100. No substring or per-state input copy is allocated, and the Boolean output has constant size.

Code

Solution.java

1class Solution {2    private Boolean[][] memo;3
4    public boolean checkValidString(String s) {5        memo = new Boolean[s.length()][s.length() + 1];6        return dfs(0, 0, s);7    }8
9    private boolean dfs(int i, int open, String s) {10        // A later star cannot repair a prefix that already closed too much.11        if (open < 0) return false;12        // Check the terminal state before indexing the n-row memo table.13        if (i == s.length()) return open == 0;14        if (memo[i][open] != null) return memo[i][open];15        char c = s.charAt(i);16        boolean ans;17        if (c == '(') {18            ans = dfs(i + 1, open + 1, s);19        } else if (c == ')') {20            ans = dfs(i + 1, open - 1, s);21        } else {22            // OR short-circuits once any opening, closing, or empty choice works.23            ans = dfs(i + 1, open + 1, s)24                || dfs(i + 1, open - 1, s) || dfs(i + 1, open, s);25        }26        memo[i][open] = ans;27        return ans;28    }29}

Hints

Hint 1

A star triples the possibilities, but you only need to know how many open brackets could plausibly be pending.

Hint 2

Track the smallest and the largest open counts consistent with the prefix read so far.

Hint 3

A ) lowers both bounds and a * lowers the low bound while raising the high bound; clamp a negative low bound to zero and fail fast on a negative high bound.

Edge Cases

A single * and an all-star string are valid by making every star empty.
A single opening or 100 openings is invalid because no assignment can close them.
A leading closing bracket, including ")*", fails immediately; later stars cannot fix its prefix.
In "*(", the star appears too early to close the final opening. Ordering matters even when total counts could match.
For "(*)", the star must be empty, so checking only its bracket interpretations loses a valid solution.
A 100-character string of 50 openings followed by 50 closings exercises the maximum balance and deepest recursion.

Common Mistakes and Interview Tips

Choosing one permanent meaning for each star greedily can discard the only solution. Preserve the full feasible balance interval.
Clamping high to zero masks an empty feasible set and wrongly accepts strings such as ")*". Reject negative high first.
Leaving low negative keeps invalid prefix histories. For example, the single star must retain zero as its minimum feasible balance.
Returning high == 0 rejects "*" even though an empty assignment works. Test whether zero is feasible, using low == 0.
In memoization, checking cached values by truthiness loses cached false results; distinguish uncomputed entries explicitly.
Aliasing memo rows in Python or JavaScript corrupts position-specific results. Allocate an independent row for each position.
Interview tip: explain why reachable counts have no gaps; interval compression is correct here because a star includes the zero change as well as both bracket changes.

Key Takeaway

When one symbol fans out into many possibilities, tracking the whole interval of reachable balances replaces exponential branching with two running numbers.