Valid Parenthesis String

Problem

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' 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 '*'.

Solution

Approach: Greedy with Min/Max Balance

The key insight is to track the minimum and maximum possible number of open parentheses, treating ‘*’ optimally for each bound.

Implementation

class Solution:
    def checkValidString(self, s: str) -> bool:
        # Track min and max possible open parentheses count
        min_open = 0
        max_open = 0

        for char in s:
            if char == '(':
                min_open += 1
                max_open += 1
            elif char == ')':
                min_open -= 1
                max_open -= 1
            else:  # char == '*'
                min_open -= 1  # Treat as ')'
                max_open += 1  # Treat as '('

            # If max_open < 0, too many ')'
            if max_open < 0:
                return False

            # min_open can't go below 0 (can't have negative open parens)
            min_open = max(min_open, 0)

        # At the end, min_open should be 0 (all parens matched)
        return min_open == 0

Approach 2: Two Pass (Left and Right)

class Solution:
    def checkValidString(self, s: str) -> bool:
        # Left to right: check we never have more ')' than '(' + '*'
        balance = 0
        for char in s:
            if char in '(*':
                balance += 1
            else:
                balance -= 1
            if balance < 0:
                return False

        # Right to left: check we never have more '(' than ')' + '*'
        balance = 0
        for char in reversed(s):
            if char in ')*':
                balance += 1
            else:
                balance -= 1
            if balance < 0:
                return False

        return True

Approach 3: Dynamic Programming

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        # dp[i][j] = can substring s[i:j+1] be valid
        dp = [[False] * n for _ in range(n)]

        # Single character: valid if it's '*'
        for i in range(n):
            if s[i] == '*':
                dp[i][i] = True

        # Empty string is valid
        for i in range(n + 1):
            for j in range(i):
                if i - 1 >= 0 and j + 1 < n:
                    dp[i-1][j+1] = dp[i-1][j+1] or False

        # Two characters
        for i in range(n - 1):
            if (s[i] == '(' or s[i] == '*') and (s[i+1] == ')' or s[i+1] == '*'):
                dp[i][i+1] = True
            if s[i] == '*' and s[i+1] == '*':
                dp[i][i+1] = True

        # Longer substrings
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                # Case 1: s[i] and s[j] form a pair
                if (s[i] in '(*') and (s[j] in ')*'):
                    if i + 1 > j - 1:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i][j] or dp[i+1][j-1]

                # Case 2: split into two parts
                for k in range(i, j):
                    dp[i][j] = dp[i][j] or (dp[i][k] and dp[k+1][j])

        return dp[0][n-1] if n > 0 else True

Complexity Analysis

Greedy Approach:

Time Complexity: O(n), single pass through string.
Space Complexity: O(1), constant extra space.

Two Pass Approach:

Time Complexity: O(n), two passes through string.
Space Complexity: O(1).

DP Approach:

Time Complexity: O(n³), filling n² table with O(n) work per cell.
Space Complexity: O(n²) for dp table.

Key Insights

Range of Possibilities: Track minimum and maximum possible open parentheses count.
Optimistic and Pessimistic: For ‘*’, optimistically treat as ‘(‘ for max_open, pessimistically as ‘)’ for min_open.
Balance Bounds: If max_open < 0, we have too many ‘)’. If min_open can’t reach 0 at end, we have unmatched ‘(‘.
Greedy Validity: The greedy approach works because we only need to know if any valid interpretation exists, not find the specific one.
Two-Pass Alternative: Check left-to-right (no excess ‘)’) and right-to-left (no excess ‘(‘).
‘*’ Flexibility: The wildcard can be empty, ‘(‘, or ‘)’, giving us multiple valid interpretations.