The problem
A string has "(", ")" and "*". A star can be "(", ")" or nothing. Can the string be a valid bracket string?
Input: "(*))"
Output: true (the star acts as "(")Picture it
Instead of trying every choice for every star, track a range: the fewest and the most brackets that could still be open. "(" raises both, ")" lowers both, and "*" lowers the minimum and raises the maximum. If the maximum ever goes negative, too many closers. The minimum is never allowed below 0. At the end, a minimum of 0 means it can be valid.
How to recognise it
- It is the "valid brackets" check, but with a wildcard
*that can be(,)or nothing. - The ordinary solution is a running balance that never drops below zero and ends at zero. The wildcard turns that single number into a range of possible balances.
- Up to 100 characters, with possibly many stars: choosing a meaning for each star one by one branches 3 ways each time.
- Whenever a choice at each step only moves a counter by a fixed amount, track the smallest and largest values it could have instead of every choice.
Start with brute force
Try all three meanings of every star (3^k combinations for k stars), and check each resulting string with a plain balance counter.
def valid_brute(s, options=("(", ")", "")):
stars = [i for i, c in enumerate(s) if c == "*"]
for pick in product(options, repeat=len(stars)):
t = list(s)
for i, p in zip(stars, pick):
t[i] = p
bal = 0; ok = True
for c in t:
bal += 1 if c == "(" else -1 if c == ")" else 0
if bal < 0:
ok = False; break
if ok and bal == 0:
return True
return False
With k stars there are 3^k strings, each checked in O(n). Ten stars is 59,049 strings, and a string of 100 stars would need about 5 × 10^47. Space is O(n) for the rebuilt string.
From brute force to the idea
- Think in balances. After each character, the number of unmatched
(can be many different values depending on what the stars were. Only the lowest and highest possible values matter, because every value in between is also possible. - Update the range. A
(raises bothloandhiby 1. A)lowers both by 1. A*could be)(lowers), nothing, or((raises), solodrops by 1 andhirises by 1. - Too many closers. If
hi < 0, even the most helpful stars cannot make the string valid: too many)have come. ReturnFalseimmediately. - Clamp the low end. A balance below 0 is not allowed, so the lowest useful value is 0:
lo = max(lo, 0). This means the star was treated as nothing (or() when it would have gone negative. - Finish. At the end, the string is valid if 0 is a possible balance, which (given the clamp) means
lo == 0.
This is the key idea: keep the range of possible open-bracket counts, fail if its top goes below zero, and succeed if its bottom reaches zero at the end.
The key idea
Greedy with (lo, hi) open-count bounds. O(n), O(1) memory.
Python solution
def check_valid_string(s):
lo = hi = 0 # range of possible open brackets
for ch in s:
if ch == "(": lo, hi = lo + 1, hi + 1
elif ch == ")": lo, hi = lo - 1, hi - 1
else: lo, hi = lo - 1, hi + 1 # * could be ), nothing, or (
if hi < 0:
return False # too many ) whatever the stars are
lo = max(lo, 0)
return lo == 0In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n × 3^k): every star assignment is built and scanned | O(n): the rebuilt string |
| Range of balances (shown code) | O(n): one pass with a few additions per character | O(1): two integers |
Edge cases
- Empty string: returns
True. - Only a star (
"*"): returnsTrue(the star is nothing). - Lone brackets (
"(",")"): both returnFalse. - Wrong order (
")("): returnsFalse;hibecomes −1 at the first)."*("also returnsFalse, since the final(stays open. - A star as a closer (
"(*)"and"(*))"): both returnTrue(the second makes the star a(). - A star as an opener (
"(*","*)"): both returnTrue. - Only stars (
"****"): returnsTrue.
Common mistakes
- Dropping the clamp
lo = max(lo, 0):"(*)"then returnsFalse, becauseloends at −1. - Returning
lo == hiorhi == 0at the end instead oflo == 0. - Checking
lo < 0for failure instead ofhi < 0. A lowlocan be repaired by stars; a lowhicannot. - Treating every star as
(in a single check, which fails"(*)"; treating every star as)fails"*)".
Now each * must become exactly ( or ) (it cannot be empty). Is the string valid? For "(*)" the answer is False and for "(*))" it is True. Describe your approach, then write it if you like.
Compare with our answer
Every star now changes the balance by exactly one, so the length must be even (an odd length can never end at 0). The range update itself stays the same.
def check_star_not_empty(s):
if len(s) % 2:
return False
lo = hi = 0
for ch in s:
if ch == "(": lo, hi = lo + 1, hi + 1
elif ch == ")": lo, hi = lo - 1, hi - 1
else: lo, hi = lo - 1, hi + 1
if hi < 0:
return False
lo = max(lo, 0)
return lo == 0
check_star_not_empty("(*))") is True, check_star_not_empty("(*)") is False and check_star_not_empty("**") is True. Time O(n), space O(1).
A strong answer mentions: the extra parity test (an odd length can never balance), reusing the lo/hi range, and why the same update still works.
1. A message contains (, ) and wildcard * characters, where a wildcard may be (, ) or nothing, and the message has up to 100 characters. Which approach fits best?
The possible balance values form a range, so tracking its two ends is O(n). A fixed replacement can miss valid strings, and counting ignores order (")(" has equal counts but is invalid). Generating all replacements is exponential.
2. What does a ) do to the range, and why does hi < 0 mean failure?
A ) lowers every possible balance by 1. If even the highest balance hi is negative, then no assignment of stars can fix it, so the answer is False.
3. A learner deletes the line lo = max(lo, 0). For which input does the function now return the wrong answer?
For "(*)" the lower bound goes 1, 0, −1 and the final check lo == 0 fails, so the function returns False although the star can be nothing. The other three inputs give the right answers (True, False, False) either way.
Score 60% or more and the lesson is marked complete.