Valid Parenthesis String

Difficulty: Medium Source: NeetCode

Problem

Given a string s containing '(', ')', and '*', return true if it’s valid. The rules are:

• Any left parenthesis '(' must have a corresponding right parenthesis.
• Any right parenthesis ')' must have a corresponding left parenthesis.
• '*' can be treated as '(', ')', or an empty string.

Example 1: Input: s = "()" Output: true

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Stack-based parenthesis matching — classic valid parentheses problem
• Greedy range tracking — maintaining a range of possible open counts

1. Brute Force / Recursive

Intuition

Try all possible interpretations of '*'. For each '*', branch into three possibilities: treat as '(', ')', or empty. Recurse and check if any interpretation leads to a valid string. This is O(3^n) in the worst case.

Algorithm

1. Define dfs(i, open_count):
   • Base: i == len(s) → return open_count == 0.
   • If open_count < 0, return False.
   • If s[i] == '(': dfs(i+1, open+1).
   • If s[i] == ')': dfs(i+1, open-1).
   • If s[i] == '*': try all three.
2. Return dfs(0, 0).

Solution

def checkValidString(s):
    def dfs(i, open_count):
        if open_count < 0:
            return False
        if i == len(s):
            return open_count == 0
        if s[i] == '(':
            return dfs(i + 1, open_count + 1)
        elif s[i] == ')':
            return dfs(i + 1, open_count - 1)
        else:  # '*'
            return (dfs(i + 1, open_count + 1) or  # treat as '('
                    dfs(i + 1, open_count - 1) or  # treat as ')'
                    dfs(i + 1, open_count))         # treat as empty

    return dfs(0, 0)


print(checkValidString("()"))     # True
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True
print(checkValidString("((*)"))   # True
print(checkValidString("(()))"))  # False

Complexity

• Time: O(3^n) — three branches per '*'
• Space: O(n) — recursion depth

2. Greedy — Track Range of Valid Open Counts

Intuition

Instead of branching, track a range [lo, hi] of possible open bracket counts at each position. lo is the minimum possible open count (assuming all '*'s are ')' or empty), and hi is the maximum (assuming all '*'s are '(').

• '(' increments both lo and hi.
• ')' decrements both.
• '*' decrements lo (treat as ')') but increments hi (treat as '(').

If hi < 0 at any point, there are too many closing brackets — invalid. Clamp lo to max(lo, 0) since negative open counts are meaningless. At the end, valid if lo == 0 (the minimum achievable open count is 0).

Algorithm

1. lo = hi = 0.
2. For each char c in s:
   • If '(': lo += 1, hi += 1.
   • If ')': lo -= 1, hi -= 1.
   • If '*': lo -= 1, hi += 1.
   • If hi < 0, return False.
   • lo = max(lo, 0).
3. Return lo == 0.

Solution

def checkValidString(s):
    lo = hi = 0  # [min possible opens, max possible opens]

    for c in s:
        if c == '(':
            lo += 1
            hi += 1
        elif c == ')':
            lo -= 1
            hi -= 1
        else:  # '*'
            lo -= 1  # best case: treat as ')'
            hi += 1  # worst case: treat as '('

        if hi < 0:
            return False  # even max opens < 0, too many ')'
        lo = max(lo, 0)   # open count can't be negative

    return lo == 0  # minimum achievable open count is 0


print(checkValidString("()"))       # True
print(checkValidString("(*)"))      # True
print(checkValidString("(*))"))     # True
print(checkValidString("((*)"))     # True
print(checkValidString("(()))"))    # False
print(checkValidString(""))         # True
print(checkValidString("*"))        # True
print(checkValidString("**"))       # True
print(checkValidString("*(("))      # False

Complexity

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

Common Pitfalls

Not clamping lo to max(lo, 0). If lo goes negative, it means we’d need a negative number of unmatched (s — which is impossible. Clamp it to 0 to keep the range valid.

Checking lo < 0 instead of hi < 0. hi is the maximum achievable open count. If even the maximum is negative, no valid interpretation exists. lo going negative is normal and handled by clamping.

Returning lo == 0 and hi == 0 at the end. Only lo == 0 is required. If lo == 0 but hi > 0, there are valid interpretations (the '*'s can absorb the remaining opens). Requiring hi == 0 would be overly strict.