Problem Statement

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 "".

Additional information

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

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "(*)"

Output: true

Explanation: The '*' can be treated as an empty string.

Example 3:

Input: s = "(*))"

Output: true

Explanation: The '*' can be treated as a left parenthesis '(' to balance the extra right parenthesis.

Top-Down Dynamic Programming (Memoization)

Intuition

Without the '*' wildcard, verifying parentheses is simple: we just keep a running count of open parentheses. If we see '(', we increment. If we see ')', we decrement. If the count ever drops below 0, or doesn't end exactly at 0, the string is invalid.

Because the '*' can represent three completely different things ('(', ')', or ""), our single path splits into three alternate realities whenever we encounter one. We can simulate all of these realities using a recursive Depth-First Search (DFS).

To prevent checking the exact same state multiple times (which would result in an exponential Time Limit Exceeded error), we use a memo dictionary. We cache our results based on our current index i in the string and our current open_count.

Algorithm

1. Initialize a memo dictionary.
2. Define a recursive helper function dfs(i, open_count):

• Base Case 1: If open_count < 0, return False (we closed more parentheses than we opened).
• Base Case 2: If i == len(s), return open_count == 0 (we reached the end, check if everything is balanced).
• If the state (i, open_count) is already in memo, return its cached result.
• If s[i] == "(": Recursively call dfs(i + 1, open_count + 1).
• If s[i] == ")": Recursively call dfs(i + 1, open_count - 1).
• If s[i] == "*": We try all three possibilities. If any of them return True, this branch is valid!
• Treat as (: dfs(i + 1, open_count + 1)
• Treat as ): dfs(i + 1, open_count - 1)
• Treat as "": dfs(i + 1, open_count)

3. Cache the result in memo[(i, open_count)] and return it.
4. Call dfs(0, 0) and return the answer.

def check_valid_string(s: str) -> bool:
    memo = {}
    
    def dfs(i, open_count):
        if open_count < 0:
            return False
            
        if i == len(s):
            return open_count == 0
            
        if (i, open_count) in memo:
            return memo[(i, open_count)]
            
        if s[i] == "(":
            res = dfs(i + 1, open_count + 1)
        elif s[i] == ")":
            res = dfs(i + 1, open_count - 1)
        else:
            # The '*' wildcard branching
            res = (dfs(i + 1, open_count + 1) or 
                   dfs(i + 1, open_count - 1) or 
                   dfs(i + 1, open_count))
                   
        memo[(i, open_count)] = res
        return res
        
    return dfs(0, 0)

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: The memo cache tracks two variables: the index i (which goes from 0 to N) and the open_count (which in the worst case can also go up to N). Thus, there are at most N^2 unique states to compute.

• Space complexity: O(N^2)

• Reason: The memo dictionary can store up to N^2 unique states, and the recursion stack can go up to N levels deep.

Greedy Range Tracking - Optimal

Intuition

Instead of exploring every alternate reality and tracking exact counts, we can just track the range of possible open parentheses!

We maintain two variables:

• left_min: The minimum possible number of open parentheses we currently have.
• left_max: The maximum possible number of open parentheses we currently have.

When we see a (, both left_min and left_max strictly increase. When we see a ), both strictly decrease.
When we see a *, left_max increases (if we imagine it's a () and left_min decreases (if we imagine it's a )).

If left_max ever drops below 0, it means that even if we turned every single wildcard into a (, we still have too many ). The string is completely invalid!
If left_min drops below 0, it means we might have been too aggressive in turning our wildcards into ). Because wildcards can just be empty strings "", we simply reset left_min to 0 and continue.

Algorithm

1. Initialize left_min = 0 and left_max = 0.
2. Iterate through each character c in the string s.
3. If c == "(": Increment both left_min and left_max by 1.
4. If c == ")": Decrement both left_min and left_max by 1.
5. If c == "*": Decrement left_min by 1 and increment left_max by 1.
6. Validation Check: If left_max < 0, there are unequivocally too many closing parentheses. Return False.
7. Correction Check: If left_min < 0, reset left_min = 0. We cannot have a negative amount of required open parentheses; we simply choose not to use the wildcards as ).
8. After processing the entire string, return True if left_min == 0 (meaning it's perfectly possible to balance the string). Otherwise, return False.

def check_valid_string(s: str) -> bool:
    left_min = 0
    left_max = 0
    
    for c in s:
        if c == "(":
            left_min += 1
            left_max += 1
        elif c == ")":
            left_min -= 1
            left_max -= 1
        else:
            left_min -= 1
            left_max += 1
            
        # If the absolute maximum possible open count is negative, it's invalid
        if left_max < 0:
            return False
            
        # We can't have negative open parentheses, so treat the excess '*' as empty strings
        if left_min < 0:
            left_min = 0
            
    # If the minimum possible open count is 0, we found a valid balance
    return left_min == 0

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the string exactly once. Operations inside the loop are simple constant-time arithmetic.

• Space complexity: O(1)

• Reason: We only use two integer variables (left_min and left_max) to track the state, completely bypassing the need for a 2D cache array.