2116. Check if a Parentheses String Can Be Valid
Medium
A parentheses string is a non-empty string consisting only of
'(' and ')'. It is valid if any of the following conditions is true:- It is
(). - It can be written as
AB(Aconcatenated withB), whereAandBare valid parentheses strings. - It can be written as
(A), whereAis a valid parentheses string.
You are given a parentheses string
s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,- If
locked[i]is'1', you cannot changes[i]. - But if
locked[i]is'0', you can changes[i]to either'('or')'.
Return
true if you can make s a valid parentheses string. Otherwise, return false.Example 1:
Input: s = "))()))", locked = "010100"
Output:
true
Explanation:
locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
Example 2:
Input: s = "()()", locked = "0000"
Output:
true
Explanation:
We do not need to make any changes because s is already valid.
Example 3:
Input: s = ")", locked = "0"
Output:
false
Explanation:
locked permits us to change s[0].
Changing s[0] to either '(' or ')' will not make s valid.
Constraints:
n == s.length == locked.length1 <= n <= 105s[i]is either'('or')'.locked[i]is either'0'or'1'.
func canBeValid(s string, locked string) bool {
if len(s) % 2 == 1 { return false }
left, right := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '(' || locked[i] == '0' {
left++
} else {
left--
}
if left < 0 { return false }
}
if left == 0 { return true }
for i := len(s) - 1; i >= 0; i-- {
if s[i] == ')' || locked[i] == '0' {
right++
} else {
right--
}
if right < 0 { return false }
}
return true
}