# 2116. Check if a Parentheses String Can Be Valid

## Problem Description

The given problem involves determining whether a string of parentheses `s` can be transformed into a valid parentheses string given certain constraints. A valid parentheses string is defined as follows:

1. It is a single pair of parentheses, i.e., "()".
2. It can be decomposed into two valid parentheses strings, `A` and `B`, arranged side-by-side as `AB`.
3. It can be a valid parentheses string `A` enclosed within a pair of parentheses, like `(A)`.

In addition to the string `s`, there is a binary string `locked`, with the same length as `s`. Each position `i` in `locked` can either be a `'1'` or a `'0'`. If `locked[i]` is `'1'`, the corresponding character `s[i]` is fixed and cannot be changed. However, if `locked[i]` is `'0'`, then `s[i]` can be converted to either `'('` or `')'`.

The goal is to determine if it's possible to make `s` a valid parentheses string by potentially changing some of the parentheses at positions where `locked[i]` is `'0'`.

## Intuition

To solve this problem, the solution employs a two-pass scan (one from left to right, and another from right to left) to count if there could be enough parentheses to balance each other out while respecting the constraints imposed by the `locked` string.

The first for loop goes from left to right. It tries to validate that there are enough left parentheses or flexible positions (where `locked[i] == '0'`) to match with potential right parentheses. Whenever a '`(`' or a flexible position is encountered, it is counted as a potential left parenthesis (increment `x`). Whenever a '`)`' is encountered in a non-flexible position, it is matched with a potential left parenthesis (decrement `x`). If at any point `x` becomes negative, it implies there are more right parentheses than can be matched by left ones, violating the balance required for a valid parentheses string.

The left to right pass ensures that at each point from left to right, there are never more right parentheses than left/flexible ones to match them.

The second for loop goes from right to left. It performs the same check but in the other direction, confirming that there are enough right parentheses or flexible positions to match with all the left parentheses.

The scan from right to left validates that there are never more left parentheses than right/flexible ones to match them from right to left.

By using two passes, we ensure the balance of parentheses is maintained in both directions. If both passes succeed without the balance going negative at any point, it guarantees that we can rearrange the parentheses (for positions where `locked[i] == '0'`) to form a valid parentheses string.

The solution also includes an initial check for strings with an odd length, as they cannot possibly form valid parentheses pairings, and such cases return `False` immediately.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input `56`?

``````1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27``````
``````1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30``````
``````1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30``````

## Solution Approach

The implementation of the solution uses a single counter variable `x` to keep track of the balance of parentheses during the two-pass scan process. The solution does not require complex data structures or patterns. It relies on simple iteration and condition evaluation. Here's the breakdown of the solution approach:

1. Initial Length Check: Before any scanning, we check if the length of the string `s` is odd. Since valid parentheses strings must have an even length (each '`(`' must have a matching '`)`'), an odd length string can never be valid. If the length is odd, we return `False`.

``````1n = len(s)
2if n & 1:
3    return False``````
2. Left to Right Scan:

• Loop through the string from the first character to the last. For each character, check if it's a left parenthesis '`(`' or a flexible position (where `locked[i] == '0'`). In either case, this could potentially be a left parenthesis, so increment the counter `x`.
• If the character is a right parenthesis '`)`' and is locked, check if there is a previously counted left parentheses to match with it by checking if `x` is greater than `0`. If yes, decrement `x`. If `x` is `0`, it means there are too many right parentheses, so the string cannot be valid.
``````1x = 0
2for i in range(n):
3    if s[i] == '(' or locked[i] == '0':
4        x += 1
5    elif x:
6        x -= 1
7    else:
8        return False``````
3. Right to Left Scan:

• Now, we do the reverse. Loop through the string from the last character to the first. If we encounter a right parenthesis '`)`' or a flexible position, it could potentially be a right parenthesis, so increment `x`.
• If the character is a left parenthesis '`(`' and is locked, check if there is a right parenthesis available to pair with it. If `x` is greater than `0`, decrement `x`. If `x` is `0`, it again means an imbalance, and the string cannot be valid.
``````1x = 0
2for i in range(n - 1, -1, -1):
3    if s[i] == ')' or locked[i] == '0':
4        x += 1
5    elif x:
6        x -= 1
7    else:
8        return False``````
4. Final Validation: If neither the left-to-right scan nor the right-to-left scan has returned `False`, the parentheses can potentially be balanced by substituting '(`' or '`)`' at the flexible positions (`'0'`in`locked`). Hence, the function returns `True`.

By methodically scanning the input from both directions, the algorithm ensures the string maintains a balance of parentheses that aligns with the rules of a valid string, considering the constraints given by `locked`. This two-pass approach is a common pattern for validating parentheses strings, often used because it efficiently verifies the balance of parentheses without needing additional storage or complex operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

### Example Walkthrough

Let's walk through an example to illustrate the solution approach with a given string `s` and a corresponding `locked` string.

Suppose we are given the string `s = "))(("` and the `locked` string `locked = "1001"`. The goal is to determine whether we can make `s` a valid parentheses string.

Before we begin with the two scans, we notice that the length of `s` is even, which means it's possible (in terms of length) for `s` to be a valid parentheses string. The initial length check passes.

Left to Right Scan:

• Starting with `x = 0`, we iterate from left to right.
• `s[0] = ')'` and `locked[0] = '1'`. Because `s[0]` is a right parenthesis and is locked, we cannot change it and there's no left parenthesis to match with it (`x = 0`). Hence, this immediately makes the string invalid and the function would return `False`.

In this example, the left-to-right scan fails at the first character itself since it encounters a locked right parenthesis with no possible left parenthesis to pair with. Hence, we do not need to move forward with the right-to-left scan, and we can conclude that it's not possible to transform `s` into a valid parentheses string with the given `locked` constraints.

## Solution Implementation

``````1class Solution:
2    def canBeValid(self, s: str, locked: str) -> bool:
3        # The length of the string s.
4        string_length = len(s)
5
6        # A valid string must have an even number of characters.
7        if string_length % 2 != 0:
8            return False
9
10        # Counter for unbalanced open parentheses.
11        balance = 0
12
13        # First pass to check if we can balance from left to right.
14        for index in range(string_length):
15            # If we encounter an open parenthesis or an unlocked character, we increment balance.
16            if s[index] == '(' or locked[index] == '0':
17                balance += 1
18            # If we can match an open parenthesis, we decrement balance.
19            elif balance:
20                balance -= 1
21            # If balance is 0 and we encounter a closed parenthesis that is locked, it is unbalanced and can't be valid.
22            else:
23                return False
24
25        # If after the first pass, we have managed to match every parenthesis, the string may be valid.
26        # However, we need to check the same from right to left.
27
28        # Reset balance for the second pass.
29        balance = 0
30
31        # Second pass to check if we can balance from right to left.
32        for index in range(string_length - 1, -1, -1):
33            # If we encounter a closed parenthesis or an unlocked character, we increment balance.
34            if s[index] == ')' or locked[index] == '0':
35                balance += 1
36            # If we can match a closed parenthesis, we decrement balance.
37            elif balance:
38                balance -= 1
39            # If balance is 0 and we encounter an open parenthesis that is locked, it is unbalanced and can't be valid.
40            else:
41                return False
42
43        # If both passes are successful, the string is valid.
44        return True
45``````
``````1class Solution {
2
3    // Method to determine if a string can be made valid by swapping parentheses
4    public boolean canBeValid(String s, String locked) {
5        int n = s.length();
6
7        // If the length of the string is odd, it can't be a valid string of parentheses
8        if (n % 2 == 1) {
9            return false;
10        }
11
12        // Initialize the balance counter for left-to-right scan
13        int balance = 0;
14
15        // Left-to-right scan to ensure all ')' can be matched
16        for (int i = 0; i < n; ++i) {
17            // If we have an unlocked character or a '(', we can potentially match a ')'
18            if (s.charAt(i) == '(' || locked.charAt(i) == '0') {
19                ++balance;
20            } else if (balance > 0) {
21                // We have a locked ')' and we have an earlier '(', so pair them
22                --balance;
23            } else {
24                // Mismatched ')' which cannot be matched
25                return false;
26            }
27        }
28
29        // Reset the balance counter for right-to-left scan
30        balance = 0;
31
32        // Right-to-left scan to ensure all '(' can be matched
33        for (int i = n - 1; i >= 0; --i) {
34            // If we have an unlocked character or a ')', we can potentially match a '('
35            if (s.charAt(i) == ')' || locked.charAt(i) == '0') {
36                ++balance;
37            } else if (balance > 0) {
38                // We have a locked '(' and we have an earlier ')', so pair them
39                --balance;
40            } else {
41                // Mismatched '(' which cannot be matched
42                return false;
43            }
44        }
45
46        // If all the checks pass, the string can be made valid
47        return true;
48    }
49}
50``````
``````1class Solution {
2public:
3    // Function to determine if the string can be made valid by swapping brackets
4    bool canBeValid(string s, string locked) {
5        int n = s.length(); // n is the length of the input string
6
7        // If the length of the string is odd, it is not possible to have a valid set of brackets
8        if (n % 2 != 0) {
9            return false;
10        }
11
12        // Forward scan: from the beginning to check if we can make a valid string
13        int openBrackets = 0; // Track the balance of open brackets
14        for (int i = 0; i < n; ++i) {
15            // If the current character is an open bracket or it is unlocked, increase the count of open brackets
16            // Unlocked characters '0' are treated as wildcards that can be either open or closed brackets
17            if (s[i] == '(' || locked[i] == '0') {
18                ++openBrackets;
19            }
20            else if (openBrackets > 0) { // If it is a closed bracket and there is an open bracket available, balance it out
21                --openBrackets;
22            }
23            else {
24                return false; // If there is no open bracket available to balance the close, it is invalid
25            }
26        }
27
28        // Backward scan: from the end to check if we can make a valid string
29        int closeBrackets = 0; // Track the balance of close brackets
30        for (int i = n - 1; i >= 0; --i) {
31            // If the current character is a closed bracket or it is unlocked, treat it similarly to the forward scan
32            if (s[i] == ')' || locked[i] == '0') {
33                ++closeBrackets;
34            }
35            else if (closeBrackets > 0) { // If there is a close bracket available to balance the open, balance it out
36                --closeBrackets;
37            }
38            else {
39               return false; // If there is no close bracket available to balance the open bracket, it is invalid
40            }
41        }
42
43        // If both scans do not detect an imbalance, the string can be made valid
44        return true;
45    }
46};
47``````
``````1// Function to determine if the string can be made valid by swapping brackets
2function canBeValid(s: string, locked: string): boolean {
3    let n: number = s.length; // n is the length of the input string
4
5    // If the length of the string is odd, it is impossible to form a valid string of brackets
6    if (n % 2 !== 0) {
7        return false;
8    }
9
10    // Forward scan: from the beginning to check if we can make a valid string
11    let openBrackets: number = 0; // Track the balance of open brackets
12    for (let i: number = 0; i < n; ++i) {
13        // If the current character is an open bracket or it is unlocked ('0'), increment open brackets
14        if (s[i] === '(' || locked[i] === '0') {
15            ++openBrackets;
16        } else if (openBrackets > 0) { // If a closing bracket is encountered and there is an open bracket to pair with, decrement
17            --openBrackets;
18        } else {
19            return false; // If there are no open brackets to pair with a closing one, it's invalid
20        }
21    }
22
23    // Backward scan: from the end to check if we can make a valid string
24    let closeBrackets: number = 0; // Track the balance of close brackets
25    for (let i: number = n - 1; i >= 0; --i) {
26        // If the current character is a closed bracket or unlocked ('0'), increment close brackets
27        if (s[i] === ')' || locked[i] === '0') {
28            ++closeBrackets;
29        } else if (closeBrackets > 0) { // If an opening bracket is encountered and there is a close bracket to pair with, decrement
30            --closeBrackets;
31        } else {
32            return false; // If there are no close brackets to pair with an opening one, it's invalid
33        }
34    }
35
36    // If both scans do not detect an imbalance, the string can be made valid
37    return true;
38}
39``````
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input `[30, 20, 10, 100, 33, 12]`?

``````1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8``````
``````1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12``````
``````1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85``````

## Time and Space Complexity

The given Python code defines a method `canBeValid` which determines if a string `s` of parentheses can be a valid expression by toggling some locked/unlocked characters defined by `locked`, where '0' represents an unlocked character and '1' represents a locked character.

### Time Complexity

The time complexity of the function is `O(n)`, where `n` is the length of the string `s`. This complexity arises from the fact that there are two separate for-loops that each iterate through the length of the string once.

1. The first loop starts from index 0 and goes up to `n - 1`.
2. The second loop starts from index `n - 1` and goes down to 0.

Neither of the loops is nested, and each pass through the entire string consists of `O(1)` operations within the loop, leading to a linear time complexity in terms of the length of the string for both passes.

Therefore, the overall time complexity of the method `canBeValid` is `O(n) + O(n)`, which simplifies to `O(n)`.

### Space Complexity

The space complexity of the function is `O(1)`. The only extra space used is for simple integer variables that are used for loop iteration and keeping track of the balance of parentheses. The space used does not scale with the size of the input string `s`, as there are no data structures dependent on `n` used for storage. All operations are done in-place with a fixed amount of extra storage space, therefore the space complexity is constant.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?