Check if a Parentheses String Can Be Valid

Problem Statement

Given a string s comprised solely of the characters '(' and ')', we need to determine if it's possible to transform this string into a valid parentheses string according to typical programming standards (balanced parentheses).

The string's transformation ability is governed by another string locked that has the same length as s. This string locked is a binary string, consisting only of '0's and '1's. The character at each position of locked signals whether the corresponding character in s can be changed:

• If locked[i] is '1', the character s[i] cannot be modified.
• If locked[i] is '0', you are free to change s[i] to either '(' or ')'.

The primary task is to determine if there is any possible combination of changes that can be made (where allowed) to make s into a valid parentheses string, wherein valid is defined as:

• Completely balanced - every opening bracket '(' has a corresponding closing bracket ')'.
• Properly nested - brackets are correctly aligned in the typical (A) format.

Examples

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.

Example 4

Input:

s = "(((())(((())", locked = "111111010111"

Output:

false

Explanation:

locked permits us to change s[6] and s[8].
We change s[6] and s[8] to ')' to make s valid.

Constraints

• n == s.length == locked.length
• 1 <= n <= 105
• s[i] is either '(' or ')'.
• locked[i] is either '0' or '1'.

Approach and Intuition

1. Initialize Counter for Flexibility: Create a balance tracker—for open and close parentheses. Also, count how many positions are flexible (i.e., marked by '0' in the locked string).

2. First Pass - Apply Fixed Characters: Traverse the string s and update the balance tracker.

   • If you encounter a fixed '(' (where locked[i] is '1'), increment the balance because you have an unpaired opening bracket.
   • If you encounter a fixed ')' (where locked[i] is '1'), decrement the balance because you have a closing bracket that needs to match an opening.
   • Track the count of changeable positions ('0' in locked) separately as changeable.

3. **Balance Check during Traversal:**If at any point during this traversal the balance goes negative, it indicates that there are more closing brackets than opening—with all options so far considered, this can't be balanced later and is invalid immediately.

4. Second Pass - Assess Flexibility's Impact:

   • After assessing the fixed characters, see if the remaining changeable positions can balance out any misalignment.
   • Since each changeable position can swing the balance by 1 (either by adding a '(' or removing a ')'), ensure that half of these changeable slots can compensate for any deficit (if the final balance count is greater than zero) or offset any excess (if balance is less than zero).

5. Achieving Balance:

   • If, after consideration of all fixed characters and potential flexible adjustments, the absolute final balance counts can be made zero through available flexible spots, the string can be transformed into a valid one. Otherwise, it can't.

This approach uses the dual traversal to assess restrictions and potentials separately, ensuring a thorough evaluation of all the positions' impact on the string's validity. The complexity is optimized by ensuring only necessary checks and counts are done predominantly in a linear pass through the string.

Solutions

class Solution {
public:
    bool validateParenthesis(string s, string lockStatus) {
        int n = s.length();
        if (n % 2 != 0) return false;
    
        int open = 0, free = 0;
        for (int i = 0; i < n; i++) {
            if (lockStatus[i] == '0') {
                free++;
            } else if (s[i] == '(') {
                open++;
            } else if (s[i] == ')') {
                if (open > 0) open--;
                else if (free > 0) free--;
                else return false;
            }
        }
    
        int checks = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (lockStatus[i] == '0') {
                checks--;
                free--;
            } else if (s[i] == '(') {
                checks++;
            } else if (s[i] == ')') {
                checks--;
            }
    
            if (checks > 0) return false;
        }
    
        return true;
    }
};