Valid Parenthesis String

Difficulty: Medium

You're given a string containing only three kinds of characters: '(', ')', and '*'. Each '*' is a wildcard that can be treated as either '(', or ')', or an empty string (nothing at all) - you choose, independently for each '*'.

Determine whether there's some way to resolve all the wildcards so that the resulting string is a valid parentheses string (every open paren has a matching close paren later, properly nested).

Examples

Input: s = "()"
Output: true

Already valid with no wildcards involved.

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

Treat the "*" as an empty string, leaving "()", which is valid.

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

Treat the "*" as "(", giving "(())", which is valid.

Constraints

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

Approach

Trying every combination of wildcard meanings is exponential. Instead of tracking one exact count of unmatched open parens, track a range of possible counts: the minimum and maximum number of unmatched '(' you could have after processing each character, given every valid choice made so far for the wildcards seen.

Scanning left to right: '(' increases both the low and high bound; ')' decreases both; '*' decreases the low bound (treat it as ')') and increases the high bound (treat it as '('). If the high bound ever drops below 0, some ')' had nothing to match no matter what - fail immediately. If the low bound drops below 0, clamp it to 0, since a count can't really be negative - it just means not every path down that low is still viable, but higher paths might be. At the end, it's valid if the low bound can reach exactly 0.

Solutions

Brute Force - Try Every Wildcard Resolution (Recursion)

At each '*', branch into all 3 possible interpretations and recursively check if any full resolution produces a valid string.

function checkValidString(s) {
  function isValid(i, openCount) {
    if (openCount < 0) return false;
    if (i === s.length) return openCount === 0;

    const c = s[i];
    if (c === "(") return isValid(i + 1, openCount + 1);
    if (c === ")") return isValid(i + 1, openCount - 1);
    // '*' — try treating it as '(', ')', or empty
    return (
      isValid(i + 1, openCount + 1) ||
      isValid(i + 1, openCount - 1) ||
      isValid(i + 1, openCount)
    );
  }
  return isValid(0, 0);
}

Time: O(3^n) in the worst case, one branch per wildcard interpretation · Space: O(n) recursion depth

Optimal - Track Range of Possible Open Counts

Instead of one open-paren count, track the minimum and maximum possible open count as you scan, widening the range for '*' and narrowing it for '(' and ')'.

function checkValidString(s) {
  let low = 0;
  let high = 0;

  for (const c of s) {
    if (c === "(") {
      low++;
      high++;
    } else if (c === ")") {
      low--;
      high--;
    } else {
      low--;
      high++;
    }

    if (high < 0) return false;
    if (low < 0) low = 0;
  }

  return low === 0;
}

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