Show problems as
Classic problem #2116MediumStringStackGreedyBracket Sequences

Check if a Parentheses String Can Be Valid

Real-world version: Can the Bracket Tape Be Balanced
Tracked in this browser only
Read Check if a Parentheses String Can Be Valid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_be_valid(tape: str, fixed: str) -> bool:
Java
public boolean canBeValid(String tape, String fixed)

More on the same topics