1079. Brackets With Wildcards
A line contains the characters (, ) and *. Each * may be read as
a single (, as a single ), or as nothing at all. Independently for each *.
Print yes if some reading makes the line balanced, or no otherwise. Balanced means every
prefix has at least as many ( as ), and the whole line has equally many of each.
(*) -> yes read the * as nothing, leaving ()
(*)) -> yes the * becomes (
((((( -> no
)*( -> no
In (*)) reading the * as ( gives (()). In )*( no reading helps, because the
leading ) can never be matched.
## What most people try first
Try all three readings of every *: 3^s for s wildcards, which is the brute force
this problem was checked against for at most twelve of them. With 200000 characters that
is hopeless.
The next instinct is a table over (position, balance). That is O(m^2) states and is
correct. The observation below collapses the whole balance dimension to two numbers.
## Track the RANGE the balance could be in
At each position, instead of one balance, carry the smallest and the largest balance any reading could produce so far.
lo = 0, hi = 0
for each character c:
if c == '(': lo += 1; hi += 1
if c == ')': lo -= 1; hi -= 1
if c == '*': lo -= 1; hi += 1 it could close, do nothing, or open
if hi < 0: answer no even the most generous reading has gone negative
if lo < 0: lo = 0 readings that dipped below zero are already dead
answer yes if lo == 0
## Why a RANGE and not a set
The set of balances achievable at a given position is the whole integer interval from lo to
hi, with no holes. That is what makes two numbers enough.
Proof by induction. At the start the set is {0}. A ( or a ) shifts every element by
the same 1, so an interval stays an interval. A * maps each element b to
{b-1, b, b+1}, and the union of those over an interval is again an interval, widened by one
at each end.
Then the pruning: any reading whose running balance goes negative is illegal and can never
recover, since balances only ever move by one and a legal string never dips below zero. So
clamping lo up to 0 discards exactly the dead readings and keeps the set an interval.
## Why the two failure tests are where they are
hi < 0 means every surviving reading has gone negative, so nothing is left. That is a
hard stop.
lo < 0 means only SOME readings have gone negative; those are discarded and the rest carry
on, which is why lo is clamped rather than the whole line rejected.
At the end, lo == 0 asks whether a reading with final balance exactly 0 survives. Since the
surviving set is the interval [lo, hi] and lo >= 0 by the clamp, that is the same as
asking whether 0 is in the interval.
## The clamp must come after the test
Clamping lo before testing hi is harmless here because the two are independent, but
clamping hi as well, or testing lo < 0 as a failure, both break the algorithm. The
input (*() is a useful trace: it ends with lo = 0 and hi = 2, and the answer is
yes.
## Where this sits
Problem #1043 counts the fewest brackets to insert into a line with no wildcards, and #1081 asks the same yes/no question with some positions LOCKED rather than free. All three are the same running-balance idea at different amounts of freedom, and #1081's proof runs in two directions rather than carrying a range.
## Overflow
lo and hi stay within plus or minus the length, 200000. The 32 bit limit of
2147483647 is not in play.
## Cost
Time O(m). Space O(1).
Constraints - `1 ≤ length ≤ 200000` - the line contains only `(`, `)` and `*`
Input
A single line containing the string, made only of the characters (, ) and *.
Output
Print the single lowercase word yes if some reading of the wildcards makes the line balanced, or no otherwise. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.