algoadvance

Given a string s containing only three types of characters: '(', ')', and ('*', write a function to check whether the string is valid. The string is considered valid if it can be converted to an empty string by applying the following rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. ‘*’ could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Your task is to implement the function checkValidString(s: str) -> bool.

Clarifying Questions

1. Can the input string s be empty?
   • Yes, an empty string is a valid input.
2. What is the maximum length of the input string s?
   • Let’s assume the input string can be up to 100 characters long.

Strategy

To solve this problem, we’ll use a greedy algorithm with two counters:

• low: Represents the minimum number of open parentheses that must be closed.
• high: Represents the maximum possible number of open parentheses.

We iterate through the string, updating low and high based on the character:

1. For '(', increment both low and high.
2. For ')', decrement both low and high.
3. For '*', decrement low (treat '*' as ')' or '') and increment high (treat '*' as '(').

After processing the string:

• low must be zero (i.e., no unbalanced open parentheses are guaranteed required).
• high must not be negative during traversal.

Code

def checkValidString(s: str) -> bool:
    low = 0
    high = 0
    for char in s:
        if char == '(':
            low += 1
            high += 1
        elif char == ')':
            if low > 0:
                low -= 1
            high -= 1
        elif char == '*':
            if low > 0:
                low -= 1
            high += 1
        if high < 0:
            return False
    return low == 0

# Example Usage:
print(checkValidString("()"))     # True
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True
print(checkValidString("((*)"))   # True

Time Complexity

• Time Complexity: O(n), where n is the length of the string. We only pass through the string once.
• Space Complexity: O(1), since we are using only a few variables for counting.

Edge Cases

1. Empty string: "" should return True.
2. String with mixed valid and invalid substrings: Check handling edge cases like "())*", "(*))((*)".

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?