class Solution {
    public boolean canBeValid(String s, String locked) {
        int len = s.length();
        int numRight = 0, numLeft = 0;  // numRight表示不可改变的右括号的数量，numLeft表示不可改变的左括号的数量

        // 如果字符串的个数为奇数，直接排除
        if (len%2==1) return false;

        // 从左往右遍历，把不可改变的右括号“安顿好”
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == ')' && locked.charAt(i) == '1') {
                numRight++;
                if (i+1-numRight < numRight) { // 该位置之前一共有r个不可改变的右括号，能够改变的括号数量为（i+1-r）
                    return false;
                }
            }
        }
        
        // 从右往左遍历，把不可改变的左括号“安顿好”
        for (int i = len-1; i >= 0; i--) {
            if (s.charAt(i) == '(' && locked.charAt(i) == '1') {
                numLeft++;
                if (len-i-numLeft < numLeft) {
                    return false;
                }
            }
        }

        // 如果都没有问题
        return true;
    }
}