Brackets With Pinned Spots

Medium

You get a string brackets made of ( and ) and a string pinned of the same length made of 0 and 1. If pinned[i] is 1, the character brackets[i] is pinned and cannot change. If it is 0, either bracket may go in that spot. A balanced bracket sequence is a non-empty string whose brackets split into pairs: every ( is closed by its own ) to the right, and pairs do not cross (for example (), (()), ()()). Return True if, by changing only unpinned characters, brackets can be made a balanced bracket sequence, and False otherwise.

Example 1

brackets=")()(", pinned="0110" → True

Positions 0 and 3 are free. Put ( and ) there to get (()).

Example 2

brackets="())(", pinned="1110" → False

The first three characters are pinned, and ()) already has more ) than (, which cannot be fixed.

Example 3

brackets="(((", pinned="000" → False

The length is odd, so no balanced sequence is possible.

Constraints

1 ≤ len(brackets) = len(pinned) ≤ 10⁵
brackets consists of ( and )
pinned consists of 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy String

Similar problems

Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Brackets With Wildcards Medium Brackets to Patch In Medium

Input

brackets=")()(", pinned="0110"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 48 tests on the server, hidden ones included.