Valid Parenthesis String
Problem
Given a string s containing only the characters '(', ')', and '*', return true if s is valid. The string is valid if all open parentheses are closed by the corresponding closing parentheses in the correct order, and '*' can represent either '(', ')', or an empty string.
- 1 ≤ s.length ≤ 100
- s[i] is '(', ')' or '*'
Example
s = "(*)"trueThe string can be interpreted as "()" by treating '*' as ')'. The algorithm maintains a range of possible counts of unmatched '(' characters as it iterates through the string. For the first character '(', the range becomes [1,1]. For '*', the range expands to [0,2] because '*' can be '(', ')' or empty. For ')', the range contracts to [0,1]. Since the minimum unmatched '(' count is zero at the end, the string is valid.
Approach
Straightforward Solution
A brute-force approach tries all interpretations of '*' as '(', ')', or empty, leading to exponential time complexity due to combinatorial explosion.
Core Observation
The problem requires checking if a string with wildcards can be balanced as parentheses. The wildcard '*' can represent multiple possibilities, so the number of unmatched '(' characters is not a single value but a range of possible counts.
Path to Optimal
The key insight is to track the minimum and maximum possible number of unmatched '(' characters as the string is processed from left to right. For each character, update this range accordingly: '(' increases both min and max, ')' decreases both, and '*' can increase max or decrease min. If at any point the maximum possible unmatched '(' count is negative, the string cannot be valid. At the end, if the minimum possible unmatched '(' count is zero, the string can be valid.
Optimal Approach
Use two counters, left_min and left_max, to track the minimum and maximum possible unmatched '(' counts. Iterate through the string, updating these counters based on the character. If left_max drops below zero, return false immediately. If left_min drops below zero, reset it to zero. After processing all characters, return true if left_min is zero, indicating a valid interpretation exists.
Time
O(n)
The algorithm makes a single pass through the string, updating counters in constant time per character.
Space
O(1)
Only a fixed number of integer counters are used, regardless of input size.
Pattern Spotlight
Greedy Algorithms (Range Tracking)
When a problem involves ambiguous characters that can represent multiple states, track the range of possible valid states instead of a single state, updating this range greedily to prune impossible paths early.
Solution
| 1 | class Solution:
|
| 2 | def checkValidString(self, s: str) -> bool:
|
| 3 | left_min, left_max = 0, 0
|
| 4 |
|
| 5 | for c in s:
|
| 6 | if c == "(":
|
| 7 | left_min, left_max = left_min + 1, left_max + 1
|
| 8 | elif c == ")":
|
| 9 | left_min, left_max = left_min - 1, left_max - 1
|
| 10 | else:
|
| 11 | left_min, left_max = left_min - 1, left_max + 1
|
| 12 |
|
| 13 | if left_max < 0:
|
| 14 | return False
|
| 15 | if left_min < 0:
|
| 16 | left_min = 0
|
| 17 |
|
| 18 | return left_min == 0 |
Step-by-Step Solution
Update Possible Unmatched '(' Range for Each Character
| 5 | for c in s:
|
| 6 | if c == "(":
|
| 7 | left_min, left_max = left_min + 1, left_max + 1
|
| 8 | elif c == ")":
|
| 9 | left_min, left_max = left_min - 1, left_max - 1
|
| 10 | else:
|
| 11 | left_min, left_max = left_min - 1, left_max + 1
|
| 13 | if left_max < 0:
|
| 14 | return False
|
| 15 | if left_min < 0:
|
| 16 | left_min = 0
|
Objective
To maintain and update the minimum and maximum possible counts of unmatched '(' characters as the string is processed.
Key Insight
By interpreting '(' as increasing unmatched count, ')' as decreasing it, and '*' as either increasing, decreasing, or leaving it unchanged, the algorithm updates left_min and left_max accordingly. This range-based tracking efficiently represents all possible interpretations of '*'. Resetting left_min to zero when it becomes negative ensures the range remains valid, reflecting that unmatched '(' cannot be negative.
Interview Quick-Check
Core Logic
Update left_min and left_max based on character: '(' increments both, ')' decrements both, '*' decrements left_min and increments left_max, capturing all wildcard possibilities.
State & Boundaries
If left_max drops below zero, return false immediately as no valid interpretation exists beyond this point.
Common Pitfalls & Bugs
Failing to reset left_min to zero when it becomes negative leads to incorrect invalidation of valid strings.
Confirm Validity by Checking Final Unmatched '(' Count
| 18 | return left_min == 0 |
Objective
To determine if the string can be valid by verifying if the minimum possible unmatched '(' count is zero after processing all characters.
Key Insight
If left_min is zero at the end, it means there exists at least one interpretation of '*' that balances all parentheses. If left_min is greater than zero, unmatched '(' remain, so the string cannot be valid. This final check leverages the range tracking to confirm the existence of a valid interpretation without enumerating all possibilities.
Interview Quick-Check
Core Logic
Return true if left_min is zero after processing the entire string, indicating a valid balanced interpretation exists.
State & Boundaries
No further checks are needed once the range is maintained correctly throughout the iteration.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if left_max < 0:Check if the maximum possible unmatched '(' count is negative.
If left_max is negative, it means even the most optimistic interpretation has more ')' than '(', making the string invalid at this point.
return left_min == 0Return true if the minimum unmatched '(' count is zero after processing all characters.
A zero minimum unmatched '(' count indicates at least one valid interpretation of '*' exists that balances the parentheses, confirming string validity.
else:If the character is '*', adjust the range to reflect all possible interpretations.
The wildcard '*' can represent '(', ')', or empty, so left_min decreases by 1 (if '*'' is ')'), and left_max increases by 1 (if '*' is '('), capturing all possibilities.
left_min, left_max = left_min - 1, left_max + 1Update left_min and left_max for '*' character by decrementing and incrementing respectively.
This range update is the core of the greedy approach, efficiently representing all interpretations of '*' without explicit enumeration.
return FalseReturn false immediately if left_max is negative.
Early termination prevents unnecessary computation once invalidity is detected, improving efficiency.
left_min, left_max = 0, 0Initialize counters for minimum and maximum possible unmatched '(' characters.
These counters represent the range of possible unmatched '(' counts considering the ambiguity of '*', enabling the algorithm to track all valid interpretations simultaneously.
if left_min < 0:Check if the minimum possible unmatched '(' count is negative.
left_min cannot be negative because unmatched '(' count cannot be less than zero; if it is, reset to zero to maintain a valid range.
left_min = 0Reset left_min to zero if it is negative.
This adjustment ensures the range remains valid and reflects that unmatched '(' cannot be negative, preserving correctness.
if c == "(":If the character is '(', increment both minimum and maximum unmatched counts.
An open parenthesis always increases the number of unmatched '(' by one, so both bounds increase accordingly.
left_min, left_max = left_min + 1, left_max + 1Update left_min and left_max by adding 1 for '(' character.
Incrementing both bounds reflects the certainty that '(' adds one unmatched '(' regardless of wildcard interpretations.
elif c == ")":If the character is ')', decrement both minimum and maximum unmatched counts.
A closing parenthesis reduces the number of unmatched '(' by one, so both bounds decrease accordingly.
left_min, left_max = left_min - 1, left_max - 1Update left_min and left_max by subtracting 1 for ')' character.
Decrementing both bounds reflects the certainty that ')' closes one unmatched '(' if available.
for c in s:Iterate through each character in the input string.
Processing characters sequentially allows updating the range of unmatched '(' counts in a single pass, ensuring linear time complexity.
Test Your Understanding
Why is it necessary to track both a minimum and maximum possible count of unmatched '(' characters?
Because the wildcard '*' can represent multiple characters, the exact number of unmatched '(' at any point is uncertain; tracking a range captures all possible interpretations, allowing the algorithm to detect invalid states early and confirm validity at the end.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Valid Parenthesis String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Valid Parenthesis String drill