Skip to content

2116. Check if a Parentheses String Can Be Valid

Description

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.

 

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: true
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'.

Solutions

Solution 1: Greedy + Two Passes

We observe that a string of odd length cannot be a valid parentheses string because there will always be one unmatched parenthesis. Therefore, if the length of the string \(s\) is odd, return \(\textit{false}\) immediately.

Next, we perform two passes.

The first pass goes from left to right, checking if all '(' parentheses can be matched by ')' or changeable parentheses. If not, return \(\textit{false}\).

The second pass goes from right to left, checking if all ')' parentheses can be matched by '(' or changeable parentheses. If not, return \(\textit{false}\).

If both passes complete successfully, it means all parentheses can be matched, and the string \(s\) is a valid parentheses string. Return \(\textit{true}\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n = len(s)
        if n & 1:
            return False
        x = 0
        for i in range(n):
            if s[i] == '(' or locked[i] == '0':
                x += 1
            elif x:
                x -= 1
            else:
                return False
        x = 0
        for i in range(n - 1, -1, -1):
            if s[i] == ')' or locked[i] == '0':
                x += 1
            elif x:
                x -= 1
            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
class Solution {
    public boolean canBeValid(String s, String locked) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        int x = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '(' || locked.charAt(i) == '0') {
                ++x;
            } else if (x > 0) {
                --x;
            } else {
                return false;
            }
        }
        x = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == ')' || locked.charAt(i) == '0') {
                ++x;
            } else if (x > 0) {
                --x;
            } 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
class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();
        if (n & 1) {
            return false;
        }
        int x = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(' || locked[i] == '0') {
                ++x;
            } else if (x) {
                --x;
            } else {
                return false;
            }
        }
        x = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == ')' || locked[i] == '0') {
                ++x;
            } else if (x) {
                --x;
            } 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
func canBeValid(s string, locked string) bool {
    n := len(s)
    if n%2 == 1 {
        return false
    }
    x := 0
    for i := range s {
        if s[i] == '(' || locked[i] == '0' {
            x++
        } else if x > 0 {
            x--
        } else {
            return false
        }
    }
    x = 0
    for i := n - 1; i >= 0; i-- {
        if s[i] == ')' || locked[i] == '0' {
            x++
        } else if x > 0 {
            x--
        } 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
function canBeValid(s: string, locked: string): boolean {
    const n = s.length;
    if (n & 1) {
        return false;
    }
    let x = 0;
    for (let i = 0; i < n; ++i) {
        if (s[i] === '(' || locked[i] === '0') {
            ++x;
        } else if (x > 0) {
            --x;
        } else {
            return false;
        }
    }
    x = 0;
    for (let i = n - 1; i >= 0; --i) {
        if (s[i] === ')' || locked[i] === '0') {
            ++x;
        } else if (x > 0) {
            --x;
        } else {
            return false;
        }
    }
    return true;
}

Comments