2116. Check if a Parentheses String Can Be Valid

class Solution {
    public boolean canBeValid(String s, String locked) {
        if (s.length() % 2 > 0) {
            return false;
        }

        int leftMin = 0, leftMax = 0;
        for (int i = 0; i < s.length(); i++) {
            if (locked.charAt(i) == '1') { // 不能改
                if (s.charAt(i) == '(') {
                    leftMin++;
                    leftMax++;
                } else {
                    leftMin--;
                    leftMax--;
                }
            } else { // 可以理解为 '*'
                leftMax++;
                leftMin--;
            }
            
            if (leftMax < 0) { // 右括号太多，左括号不够用了
                return false;
            }
            // leftMin 与 leftMax 的差值由 '*' 导致
            leftMin = Math.max(0, leftMin); // 左括号数量不能为负数，此时撤销此前 '*' 替换为右括号的动作，可以用 '(*)' 加深理解
        }

        return leftMin == 0;
    }
}

DFS 也能解题，但是判题会 TLE，所以采用贪心解法实现。

References

2116. Check if a Parentheses String Can Be Valid
678. Valid Parenthesis String