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
PreviewThe key insight is to track the minimum and maximum possible number of unmatched '(' characters as the string is processed from left to right…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To determine if the string can be valid by verifying if the minimum possible unmatched '(' count is zero after processing all characters.
1 more step with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why is it necessary to track both a minimum and maximum possible count of unmatched '(' characters?
See the answer with Pro.
Related Problems
Greedy Algorithms 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