Check if a Parentheses String Can Be Valid

The strings s and locked have equal length. The string s contains parentheses, and locked contains bits. At index i, a 1 in locked means the parenthesis must stay unchanged; a 0 lets you choose either ( or ) for that position. Return true if some choices make the entire string balanced. In a balanced string, no prefix has more closing than opening parentheses, and the total counts are equal. Characters cannot be inserted or removed.

In the diagrams, filled boxes are locked positions; the digits underneath are the corresponding locked bits.

Example 1:

Check if a Parentheses String Can Be Valid, example 1: illustration of the example

Input: s = "))"
locked = "00"

Output: true

Explanation: Both positions are unlocked. Change the first character to ( and keep the second as ), giving ().

Example 2:

Check if a Parentheses String Can Be Valid, example 2: illustration of the example

Input: s = ")("
locked = "11"

Output: false

Explanation: Both characters are locked. The string starts with a closing parenthesis, so it cannot be balanced.

Example 3:

Check if a Parentheses String Can Be Valid, example 3: illustration of the example

Input: s = "(()"
locked = "000"

Output: false

Explanation: A balanced string must have even length. Changing these three characters cannot change the length, so no valid result exists.

Constraints:

1 <= s.length <= 100000
s.length == locked.length
s contains only ( and ).
locked contains only 0 and 1.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.