Medium Min-Max Range Greedy
In plain English: Check if a string of parentheses with wildcards (*) can be made valid.
Track a range [lo, hi] of possible open-paren counts. '(' increments both, ')' decrements both, '*' widens the range. If hi < 0, too many ')'. If lo < 0, clamp to 0. Valid if lo == 0 at end.
Prompt
Given a string containing '(', ')' and '*' where '*' can be '(', ')' or empty, determine if the string is valid.
Try to write it from scratch before scrolling down.
Solution
def check_valid_string(s):
lo = hi = 0 # range of possible open paren counts
for ch in s:
if ch == '(':
lo += 1
hi += 1
elif ch == ')':
lo -= 1
hi -= 1
else: # '*'
lo -= 1 # treat as ')'
hi += 1 # treat as '('
if hi < 0: # too many ')'
return False
lo = max(lo, 0) # can't have negative open count
return lo == 0
# Test: check_valid_string("(*))") == True
# Test: check_valid_string("(*)") == True
# Test: check_valid_string(")(") == False