1081. Locked Positions in a Bracket String

A bracket string of length m is given, together with a lock string of the same length. A position whose lock character is 1 is FIXED and must keep its bracket; a position whose lock character is 0 is FREE and may be set to ( or ) as you like.

Print yes if the free positions can be set so the whole string is balanced, or no otherwise.

string ))())) lock 010100 -> yes string () lock 11 -> yes string )( lock 00 -> yes both positions are free string )( lock 11 -> no

## What most people try first

Try both settings of every free position: 2^f, which is the brute force this problem was checked against for at most fourteen free positions.

The wildcard range from #1079 also works here, since a free position behaves exactly like a * that may not be read as nothing. It is a fine solution. The two-sweep argument below is shorter and is worth having for its own sake, because the same shape answers many "is there an assignment" questions.

## Two sweeps, each maximally generous in one direction

``` if m is odd: answer no

left to right: treat every FREE position as '(' keep a running balance; if it ever goes negative, answer no

right to left: treat every FREE position as ')' keep a running balance counting ')' as +1 and '(' as -1 if it ever goes negative, answer no

answer yes ```

## What each sweep actually checks

A balanced string needs two things: no prefix with more ) than (, and no SUFFIX with more ( than ). Together with an even length, those two conditions are exactly balancedness.

The first sweep asks whether the prefix condition is satisfiable. It sets every free position to (, the most generous possible choice for that condition, so if the balance still goes negative then the locked ) characters alone already outnumber everything before them and no assignment can help.

The second sweep does the same for the suffix condition, setting every free position to ).

## Why satisfying each condition separately is enough

The two sweeps make opposite assumptions, so it is not obvious that ONE assignment satisfies both. It does, and the construction is explicit.

Write f for the number of free positions, L for the locked ( count and R for the locked ) count, so f + L + R = m. Applied to the whole string, the first sweep says R <= f + L, which with f + L = m - R gives R <= m/2; the second says L <= f + R and gives L <= m/2.

Set t = m/2 - L. Then t >= 0, and t <= f because m/2 - L <= m - L - R = f is exactly R <= m/2. Now set the FIRST t free positions to ( and the rest to ). The totals match: L + t = m/2 openers.

Take any prefix of length p, holding l locked openers, r locked closers and g free positions. Two cases.

If g <= t, every free position in the prefix was set to (, so the balance is l + g - r, which is exactly the number the FIRST sweep computed, and that sweep never went negative.

If g > t, then t of them are ( and g - t are ), so the balance is

l + t - r - (g - t) = l + 2t - r - g = l + m - 2L - r - g

Substituting m = f + L + R turns that into (f - g) + (R - r) - (L - l), which is (free in the suffix) + (locked closers in the suffix) - (locked openers in the suffix). That is precisely the quantity the SECOND sweep computed, and it never went negative either.

Both cases hold, so the assignment is balanced and the two sweeps are exactly the right test.

## The odd length

An odd m is impossible whatever the locks, and neither sweep detects it: on ) with a free lock the left sweep reads it as ( and never goes negative, and the right sweep reads it as ) and never goes negative either. The length test is not an optimisation.

## Overflow

Balances stay within plus or minus m = 200000. The 32 bit limit of 2147483647 is not in play.

## Cost

Time O(m). Space O(1).

Constraints - `1 ≤ m ≤ 200000` - the first line contains only `(` and `)` - the second line contains only `0` and `1` and has the same length