2116. Check if a Parentheses String Can Be Valid LeetCode Solution
In this guide, you will get 2116. Check if a Parentheses String Can Be Valid LeetCode Solution with the best time and space complexity. The solution to Check if a Parentheses String Can Be Valid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Check if a Parentheses String Can Be Valid
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: 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'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2116. Check if a Parentheses String Can Be Valid LeetCode Solution in C++
class Solution {
public:
bool canBeValid(string s, string locked) {
if (s.length() % 2 == 1)
return false;
const bool leftToRightIsOkay = check(s, locked, true);
ranges::reverse(s);
ranges::reverse(locked);
const bool rightToLeftIsOkay = check(s, locked, false);
return leftToRightIsOkay && rightToLeftIsOkay;
}
private:
bool check(const string& s, const string& locked, bool isForward) {
int changeable = 0;
int l = 0;
int r = 0;
for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
const char lock = locked[i];
if (lock == '0')
++changeable;
else if (c == '(')
++l;
else // c == ')'
++r;
if (isForward && changeable + l - r < 0)
return false;
if (!isForward && changeable + r - l < 0)
return false;
}
return true;
}
}; /* code provided by PROGIEZ */
2116. Check if a Parentheses String Can Be Valid LeetCode Solution in Java
class Solution {
public boolean canBeValid(String s, String locked) {
if (s.length() % 2 == 1)
return false;
return check(s, locked, true) && check(new StringBuilder(s).reverse().toString(),
new StringBuilder(locked).reverse().toString(), false);
}
private boolean check(final String s, final String locked, boolean isForward) {
int changeable = 0;
int l = 0;
int r = 0;
for (int i = 0; i < s.length(); ++i) {
final char c = s.charAt(i);
final char lock = locked.charAt(i);
if (lock == '0')
++changeable;
else if (c == '(')
++l;
else // c == ')'
++r;
if (isForward && changeable + l - r < 0)
return false;
if (!isForward && changeable + r - l < 0)
return false;
}
return true;
}
} // code provided by PROGIEZ
2116. Check if a Parentheses String Can Be Valid LeetCode Solution in Python
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
if len(s) % 2 == 1:
return False
def check(s: str, locked: str, isForward: bool) -> bool:
changeable = 0
l = 0
r = 0
for c, lock in zip(s, locked):
if lock == '0':
changeable += 1
elif c == '(':
l += 1
else: # c == ')'
r += 1
if isForward and changeable + l - r < 0:
return False
if not isForward and changeable + r - l < 0:
return False
return True
return check(s, locked, True) and check(s[::-1], locked[::-1], False) # code by PROGIEZ
