A parentheses string consists exclusively of the characters '(' and ')'. A string is considered valid if it meets any of these conditions:

• The string is exactly ()
• The string can be expressed as AB (concatenation of A and B), where both A and B are valid parentheses strings
• The string can be expressed as (A), where A is a valid parentheses string

Given a parentheses string s and a binary string locked of equal length, determine whether you can transform s into a valid parentheses string. For each index i:

• If locked[i] is '1', the character at position i cannot be modified
• If locked[i] is '0', the character at position i can be changed to either '(' or ')'

Examples

Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: Positions 1 and 3 are locked, so their characters cannot be modified.
We can change positions 0 and 4 to '(' while leaving positions 2 and 5 unchanged,
resulting in the valid string "(()())".

Example 2:

Input: s = "()()", locked = "0000"
Output: true
Explanation: No modifications are needed since the string is already valid.

Example 3:

Input: s = ")", locked = "0"
Output: false
Explanation: Although position 0 can be modified, changing it to either '(' or ')'
cannot produce a valid parentheses string of length 1.

Example 4:

Input: s = "(((())(((())", locked = "111111010111"
Output: true
Explanation: Positions 6 and 8 are unlocked. Converting both to ')' yields a valid string.

Observations

A valid parentheses string must satisfy several inherent properties. First, its length must be even, with exact half being opening brackets and half being closing brackets. Second, for any prefix of the string, the count of opening brackets must be at least the count of closing brackets. Third, for any suffix of the string, the count of closing brackets must be at least the count of opening brackets.

When certain positions are locked and others can be freely modified, we can apply a greedy strategy. For prefix validation, unlocked positions can be treated as opening brackets to maximize the chance of satisfying the prefix condition. For suffix validation, unlocked positions can be treated as closing brackets to maximize the chance of satisfying the suffix condition.

Algorithm

The solution involves three validation checks:

1. Length Check: If the string length is odd, it cannot form a valid parentheses string.
2. Prefix Check: Iterate from left to right, treating each position as an opening bracket unless it is a locked closing bracket. At any point, the cumulative count must never drop below zero.
3. Suffix Check: Iterate from right to left, treating each position as a closing bracket unless it is a locked opening bracket. At any point, the cumulative count must never drop below zero.

If all three checks pass, the string can be transformed into a valid parentheses string.

Complexity Analysis

The algorithm performs two linear passes through the string, resulting in O(n) time complexity where n is the length of the string. The space usage is O(1) since only a few integer counters are maintained.

Reference Implementation

public class ValidParenthesesChecker {

    public boolean canBeValid(String input, String lockStatus) {
        int length = input.length();
        if ((length & 1) == 1) {
            return false;
        }

        char[] characters = input.toCharArray();
        char[] locks = lockStatus.toCharArray();

        int balanceFromLeft = 0;
        for (int i = 0; i < length; i++) {
            boolean isLocked = locks[i] == '1';
            boolean isClosingBracket = characters[i] == ')';
            if (isLocked && isClosingBracket) {
                balanceFromLeft--;
            } else {
                balanceFromLeft++;
            }
            if (balanceFromLeft < 0) {
                return false;
            }
        }

        int balanceFromRight = 0;
        for (int i = length - 1; i >= 0; i--) {
            boolean isLocked = locks[i] == '1';
            boolean isOpeningBracket = characters[i] == '(';
            if (isLocked && isOpeningBracket) {
                balanceFromRight--;
            } else {
                balanceFromRight++;
            }
            if (balanceFromRight < 0) {
                return false;
            }
        }

        return true;
    }
}