1008MediumStringStackGreedyBracket Sequences

Can the Bracket Tape Be Balanced

Tracked in this browser only

Trains the technique from

LeetCode 2116Check if a Parentheses String Can Be Valid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape of brackets reads tape, each character either '(' or ')'. A second string fixed of the same length says which of them are settled: a '1' means that bracket cannot be altered, and a '0' means it may be replaced by either bracket.

A tape is balanced when its brackets pair off one to one, each opening bracket with a closing bracket somewhere after it, and no pairs crossing.

Return whether some choice for the alterable places leaves the tape balanced.

Examples

Example 1

Input: tape = "))((", fixed = "0110"
Output: true

The two ends are alterable and the two middle brackets are settled. Making the first place an opening and the last a closing gives a tape whose brackets pair off as two neighbouring couples.

Example 2

Input: tape = ")(", fixed = "11"
Output: false

Both brackets are settled the wrong way round, and nothing may be altered, so the closing bracket at the front has nothing before it to match.

Example 3

Input: tape = "(())", fixed = "1111"
Output: true

Every bracket is settled and the tape already pairs off, one couple inside the other.

Constraints

1 <= tape.length <= 10^5
fixed.length == tape.length
Every character of tape is a round bracket, opening or closing.
Every character of fixed is '0' or '1'.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_be_valid(tape: str, fixed: str) -> bool:

Java

public boolean canBeValid(String tape, String fixed)

The intended approach

Time O(n) over the tape's length.Space O(1).

A tape of odd length can never pair off, so that is settled at once. Otherwise sweep twice. Going from the left, count the openings that could be available: a settled opening or any alterable place adds one, since an alterable place is free to become an opening, while a settled closing takes one away. Should the count ever fall below nothing, some settled closing has nothing that could ever match it, whatever the alterable places become, so the answer is no. Then sweep from the right counting closings the same way: a settled closing or any alterable place adds one, a settled opening takes one away. Falling below nothing there means some settled opening has nothing after it that could match. Surviving both sweeps is enough. The left sweep says no front piece of the tape is short of openings, the right sweep says no back piece is short of closings, and with the length even those two together leave the alterable places able to make up the difference: any place the left sweep wants as an opening lies before any place the right sweep wants as a closing, so the two demands never fight over the same place.

Pythonentry point: can_be_valid

def can_be_valid(tape, fixed):
    n = len(tape)
    if n % 2:
        return False
    free = 0
    for at in range(n):
        if fixed[at] == '0' or tape[at] == '(':
            free += 1
        else:
            free -= 1
        if free < 0:
            return False
    free = 0
    for at in range(n - 1, -1, -1):
        if fixed[at] == '0' or tape[at] == ')':
            free += 1
        else:
            free -= 1
        if free < 0:
            return False
    return True

The obvious version

Try every way of filling the alterable places. For each filling, walk the tape keeping the depth of unmatched openings and reject it the moment the depth goes below nothing or fails to end at nothing. Reports yes at the first filling that survives. Costs two to the power of the alterable places rather than two sweeps.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_be_valid(tape, fixed):
    if len(tape) % 2:
        return False
    spots = [at for at in range(len(tape)) if fixed[at] == '0']
    for mask in range(1 << len(spots)):
        chars = list(tape)
        for bit, at in enumerate(spots):
            chars[at] = '(' if mask >> bit & 1 else ')'
        depth = 0
        ok = True
        for ch in chars:
            depth += 1 if ch == '(' else -1
            if depth < 0:
                ok = False
                break
        if ok and depth == 0:
            return True
    return False

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in