##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2116.html

# 2116. Check if a Parentheses String Can Be Valid

• Difficulty: Medium.
• Related Topics: String, Stack, Greedy.
• Similar Questions: Valid Parentheses, Generate Parentheses, Valid Parenthesis String, Minimum Remove to Make Valid Parentheses, Check if There Is a Valid Parentheses String Path.

## 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.

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.


Constraints:

• n == s.length == locked.length

• 1 <= n <= 105

• s[i] is either '(' or ')'.

• locked[i] is either '0' or '1'.

## Solution (Java, C++, Python)

• class Solution {
public boolean canBeValid(String s, String locked) {
if (s == null || s.isEmpty()) {
return true;
}
if ((s.length() & 1) > 0) {
return false;
}
if (locked == null || locked.isEmpty()) {
return true;
}
int numOfLockedClose = 0;
int numOfLockedOpen = 0;
for (int i = 0; i < s.length(); i++) {
int countOfChars = i + 1;
if (s.charAt(i) == ')' && locked.charAt(i) == '1') {
numOfLockedClose++;
if (numOfLockedClose * 2 > countOfChars) {
return false;
}
}
int j = s.length() - 1 - i;
if (s.charAt(j) == '(' && locked.charAt(j) == '1') {
numOfLockedOpen++;

if (numOfLockedOpen * 2 > countOfChars) {
return false;
}
}
}
return true;
}
}

############

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;
}
}

• 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

############

# 2116. Check if a Parentheses String Can Be Valid
# https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/

class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
n = len(s)
s = list(s)

if n & 1: return False

for i in range(n):
if locked[i] == '0':
s[i] = '#'

opened = closed = 0
for x in s:
if x == '#' or x == '(':
opened += 1
else:
closed += 1

if closed > opened:
return False

opened = closed = 0
for i in range(n - 1, -1, -1):
if s[i] == '#' or s[i] == ')':
closed += 1
else:
opened += 1

if opened > closed:
return False

return True


• 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;
}
};

• 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
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).