Problem

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

  • It is ().
  • It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
  • It can be written as (A), where A is a valid parentheses string.

You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,

  • If locked[i] is '1', you cannot change s[i].
  • But if locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if you can make s a valid parentheses string. Otherwise, return false.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|c|c|} \hline \text{Index} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline s & ) & ) & ( & ) & ) & ) \\ \hline \text{locked} & 0 & \colorbox{red} 1 & 0 & \colorbox{red} 1 & 0 & 1 \\ \hline \text{Changed} & \colorbox{RoyalBlue} ( & ) & ( & ) & \colorbox{RoyalBlue} ( & ) \\ \hline \end{array} $$

1
2
3
4

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:

1
2
3

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

Example 3:

1
2
3
4

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.

Constraints:

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

Solution

Method 1 - Using Stack

Here is the approach:

  1. Two Stacks:
    • One stack to keep track of open parentheses.
    • Another stack to keep track of flexible positions where characters can be changed.
  2. Pass through the String: Traverse the string:
    • Push the index of '(' characters onto the open stack if it is locked (locked[i] == '1'), or onto the flexible stack if it is unlocked (locked[i] == '0').
    • Push the index of ')' characters directly onto another stack if it is locked.
  3. Balancing using Stacks:
    • Try to balance each ‘)’ with the corresponding ‘(’ from the open stack first.
    • If ‘(’ is unavailable (i.e., the stack is empty), try to use a flexible position from the flexible stack.
    • Ensure that flexible positions can be used appropriately to convert to ‘(’ or ‘)’ to balance the string.
  4. Final Check:
    • Ensure all open parentheses can be balanced by available flexible positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public boolean canBeValid(String s, String locked) {
        int n = s.length();
        if (n % 2 != 0) return false;

        Stack<Integer> open = new Stack<>();
        Stack<Integer> flexible = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            if (locked.charAt(i) == '0') {
                flexible.push(i);
            } else if (s.charAt(i) == '(') {
                open.push(i);
            } else if (s.charAt(i) == ')') {
                if (!open.isEmpty()) {
                    open.pop();
                } else if (!flexible.isEmpty()) {
                    flexible.pop();
                } else {
                    return false;
                }
            }
        }
        
        // Check if all opening parentheses can be balanced with flexible positions left
        while (!open.isEmpty() && !flexible.isEmpty()) {
            if (open.peek() < flexible.peek()) {
                open.pop();
                flexible.pop();
            } else {
                return false;
            }
        }
        
        return open.isEmpty();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n: int = len(s)
        if n % 2 != 0: 
            return False

        open_stack: deque[int] = deque()
        flexible_stack: deque[int] = deque()
        
        for i in range(n):
            if locked[i] == '0':
                flexible_stack.append(i)
            elif s[i] == '(':
                open_stack.append(i)
            elif s[i] == ')':
                if open_stack:
                    open_stack.pop()
                elif flexible_stack:
                    flexible_stack.pop()
                else:
                    return False
        
        # Check if all opening parentheses can be balanced with flexible positions left
        while open_stack and flexible_stack:
            if open_stack[-1] < flexible_stack[-1]:
                open_stack.pop()
                flexible_stack.pop()
            else:
                return False
        
        return not open_stack

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string because each character is processed once.
  • 🧺 Space complexity: O(n), due to the use of stacks to hold the indices.

Method 2 - Two Pass

To determine if a string of parentheses can be transformed into a valid parentheses string given the constraints, we need to ensure that:

  1. We have an equal number of '(' and ')';
  2. At any point in parsing the string, the number of closing parentheses should not exceed the number of opening parentheses;
  3. Respect the constraints provided by the locked string.

To determine if a string of parentheses can be transformed into a valid parentheses string given the constraints, we need to ensure that:

  1. Even Length:
    • The string length must be even. If s.length() is odd, return false.
  2. Balanced Parentheses:
    • We have an equal number of '(' and ')'.
  3. No Premature Closing Parentheses:
    • At any point in parsing the string, the number of closing parentheses ')' should not exceed the number of opening parentheses '('.
  4. Respect Locked Constraints:
    • The locked string provides constraints on which parentheses can be altered. Any position where locked[i] == '1' is immutable.

Approach

  1. Forward Pass (Left to Right):
    • Track the balance of opening and closing parentheses.
    • Use two counters: open for fixed opening parentheses and flexible for flexible positions.
    • Traverse the string from left to right:
      • Increment flexible for positions that can be changed (locked[i] == '0').
      • Increment open for fixed opening parentheses '('.
      • For a closing parenthesis ')', decrement open if available; otherwise, use flexible. If neither is available, return false.
    • Ensure that at any point, the number of closing parentheses does not exceed the number of opening parentheses when considering the flexible positions.
  2. Backward Pass (Right to Left):
    • This helps balance any excess opening parentheses by utilizing available changes from the other direction.
    • Use two counters: close for fixed closing parentheses and flexible for flexible positions.
    • Traverse the string from right to left:
      • Increment flexible for positions that can be changed (locked[i] == '0').
      • Increment close for fixed closing parentheses ')'.
      • For an opening parenthesis '(', decrement close if available; otherwise, use flexible. If neither is available, return false.
    • Ensure that at any point, the number of opening parentheses does not exceed the number of closing parentheses when considering the flexible positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    public boolean canBeValid(String s, String locked) {
        int n = s.length();
        if (n % 2 != 0) return false;
            
        // Forward pass
        int open = 0, flexible = 0;
        for (int i = 0; i < n; i++) {
            if (locked.charAt(i) == '0') {
                flexible++;
            } else if (s.charAt(i) == '(') {
                open++;
            } else {
                if (open > 0) {
	                open--;
                } else if (flexible > 0) {
	                flexible--;
                } else {
	                return false;
                }
            }
        }

        // Backward pass
        int close = 0; flexible = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (locked.charAt(i) == '0') {
                flexible++;
            } else if (s.charAt(i) == ')') {
                close++;
            } else {
                if (close > 0) {
	                close--;
                } else if (flexible > 0) {
	                flexible--;
                } else {
	                return false;
                }
            }
        }
        
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n = len(s)
        if n % 2 != 0:
            return False
            
        # Forward pass
        open = 0
        flexible = 0
        for i in range(n):
            if locked[i] == '0':
                flexible += 1
            elif s[i] == '(':
                open += 1
            else:
                if open > 0:
                    open -= 1
                elif flexible > 0:
                    flexible -= 1
                else:
                    return False

        # Backward pass
        close = 0
        flexible = 0
        for i in range(n - 1, -1, -1):
            if locked[i] == '0':
                flexible += 1
            elif s[i] == ')':
                close += 1
            else:
                if close > 0:
                    close -= 1
                elif flexible > 0:
                    flexible -= 1
                else:
                    return False
        
        return True

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string since we are scanning the string twice.
  • 🧺 Space complexity: O(1), as we are using a constant amount of extra space.