Check if a Parentheses String Can Be Valid

lcpy gen -n 2116   # by problem number
lcpy gen -s check_if_a_parentheses_string_can_be_valid   # by problem name

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.

Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.

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.

Input: s = "(((())(((())", locked = "111111010111"
Output: true
Explanation: locked permits us to change s[6] and s[8].
We change s[6] and s[8] to ')' to make s valid.

class Solution:
    # Time: O(n)
    # Space: O(1)
    def can_be_valid(self, s: str, locked: str) -> bool:
        if len(s) % 2:
            return False
        low = high = 0
        for char, lock in zip(s, locked, strict=True):
            if lock == "0":
                low -= 1
                high += 1
            elif char == "(":
                low += 1
                high += 1
            else:
                low -= 1
                high -= 1
            if high < 0:
                return False
            low = max(low, 0)
        return low == 0