Balanced Bracket Check With Wildcard Characters

Medium20–25 min

Topics

StackStringGreedy

Companies

FacebookAmazonGoogle

Given a string s containing '(', ')', and '?' — where each '?' can stand in for '(', for ')', or for nothing at all — determine whether some assignment of the wildcards makes the string a balanced bracket sequence. Trying every combination of wildcard assignments is correct but explodes exponentially. The key insight that avoids it: instead of picking one interpretation for each '?' up front, track the entire range of open-bracket counts that remain simultaneously possible as the string is scanned — the fewest opens achievable so far, and the most. A '?' simply widens that range by one on each side rather than forcing a choice. As long as 0 stays reachable within the range by the end, some valid assignment exists — found in a single linear pass instead of a search tree.

Test Case 1:

Input:s = "(())?"

Output:true

Explanation:"(())" is already balanced on its own; treat '?' as nothing at all and it's still balanced.

Test Case 2:

Input:s = "?)?)"

Output:true

Explanation:Treat both '?' as '(': the string becomes '(' + ')' + '(' + ')' = "()()" — balanced.

Test Case 3:

Input:s = "(?))("

Output:false

Explanation:No assignment of '(', ')', or empty to '?' can balance this — there's a trailing unmatched '(' no matter what '?' becomes.

Constraints

◆1 ≤ s.length ≤ 20
◆s consists only of the characters '(', ')', and '?'
◆'?' may stand in for '(', for ')', or for nothing at all (an empty character)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Try Every Interpretation of Every Wildcard

Brute

Walk the string recursively, tracking how many '(' are currently open. A '(' always increments the open count; a ')' always decrements it (failing immediately if the count goes negative — too many closes). A '?' branches three ways: try it as '(', try it as ')', and try it as empty — succeeding if any one of the three leads to a fully valid string. This explores every possible assignment of every wildcard, so it's always correct, but with up to n wildcards, that's up to 3ⁿ combinations in the worst case.

TimeO(3ⁿ)

SpaceO(n)

Java

Try it out

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

    private boolean dfs(String s, int i, int open) {
        if (open < 0) return false;
        if (i == s.length()) return open == 0;
        char c = s.charAt(i);
        if (c == '(') return dfs(s, i + 1, open + 1);
        if (c == ')') return dfs(s, i + 1, open - 1);
        return dfs(s, i + 1, open + 1) || dfs(s, i + 1, open - 1) || dfs(s, i + 1, open);
    }
}

Optimal — Track a Range of Possible Open Counts

Optimal

Instead of branching on every wildcard, track the entire range of open-bracket counts that are simultaneously still possible: lo (the fewest opens if every wildcard so far became ')' or empty) and hi (the most opens if every wildcard became '('). '(' shifts both bounds up by one; ')' shifts both down by one; '?' shifts hi up and lo down (since it could be either). If hi ever dips below 0, even the most generous interpretation has too many closes — fail immediately. If lo dips below 0, that's fine — it just means the least generous interpretation over-closed, but some wildcard earlier could have been empty instead, so clamp lo back to 0 rather than failing. The string is valid if 0 is still within range at the end (lo reaches exactly 0).

TimeO(n)

SpaceO(1)