Determine whether a parentheses string with locked positions can be turned into a valid parentheses sequence.
You are given two strings of the same length:
s, consisting only of'('and')'locked, consisting only of'0'and'1'
Each position in locked tells you whether the corresponding character in s can be changed:
'1'means the character is fixed and cannot be modified'0'means you may change that character to either'('or')'
Return whether it is possible to replace the unlocked characters so that the final string is a valid parentheses string.
A valid parentheses string is one where:
- every opening parenthesis has a matching closing parenthesis
- parentheses are properly nested
- the total length is even
Input Format
Input
s: a string of parentheses characterslocked: a binary string of the same length
Interpretation
- If
locked[i] == '1',s[i]is fixed - If
locked[i] == '0',s[i]may be changed to either'('or')'
Output Format
Output
- Return
trueif the string can be made valid after changing any unlocked positions. - Otherwise return
false.
Constraints
s.length == locked.length1 <= s.length <= $10^{5}$s[i]is either'('or')'locked[i]is either'0'or'1'
Example 1
Input
s = ")()(", locked = "0101"Output
true
Explanation
The second and fourth positions are unlocked. One possible replacement is "(())", which is valid.
Example 2
Input
s = ")())", locked = "1111"
Output
false
Explanation
No characters can be changed, and the string is not a valid parentheses sequence.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.