Check if a Parentheses String Can Be Valid
Problem Statement
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
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.
Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.
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'.
We need to figure out whether we can change a particular string of parentheses into a valid parentheses or not !!
We are given a string locked, which represents whether each of the parentheses can be either altered or not based on their value. Let's see how we proceed.
Brute Force Approach
Intuition
We are given a string locked with binary values i.e. either 0 or 1. If locked[i]=0, then that particular index of the string s can be either changed to '(' or ')'.
The Brute force approach involves trying every possibilities of s[i] for every locked[i]=0. Trying every possibilities gives us the intuition of the recursive algorithm.
If we encounter that locked[i]='0', we will call 2 recursive calls, one with '(' and another with ')'. Whenever a recursive call is made we must ensure that the balance values are passed on correctly.
What is the balance variable ?
We maintain a balance variable to let us know that if the balance variable is negative, we return false. At the end of the string, if the balance variable is 0, we can say that the string is a valid parentheses.
If we encounter a '(' we increase the balance variable by 1 else we decrease it by 1.
So, at any point, if we encounter any of the valid parentheses we will return a true or else we return false.
Approach
Step 1: Function canBeValid(s, locked):
If the length of s is odd, return false (impossible to balance).
Convert s and locked to character arrays.
Call the helper function canBeValidHelper with:
- s (character array of s)
- locked (character array of locked)
- index = 0 (start from the first character)
- balance = 0 (initial balance of parentheses).
Step 2: Function canBeValidHelper(s, locked, index, balance):
Base case: If index equals the length of s:
- Return true if balance == 0, else false.
Invalid case:
- If balance < 0, return false.
When locked[index] == '1' (character is fixed):
- If s[index] == '(', increment balance by 1 and call canBeValidHelper with the next index.
- Else (s[index] == ')'), decrement balance by 1 and call canBeValidHelper with the next index.
When locked[index] == '0' (character is flexible):
- Try changing s[index] to '(': Increment balance by 1 and call canBeValidHelper with the next index.
- Try changing s[index] to ')': Decrement balance by 1 and call canBeValidHelper with the next index.
- Return true if either of the above calls returns true.
Step 3: Return the result of canBeValidHelper from the main function
Dry-Run
Input:
- s: "(()))(()"
- locked: "11000110"
Step 1: Initial Call
- Call: canBeValidHelper(s, locked, 0, 0)
- index = 0, balance = 0.
- locked[0] = '1', s[0] = '(': Increase balance to 1.
- Next Call: canBeValidHelper(s, locked, 1, 1).
Step 2: Second Call
- Call: canBeValidHelper(s, locked, 1, 1)
- index = 1, balance = 1.
- locked[1] = '1', s[1] = '(': Increase balance to 2.
- Next Call: canBeValidHelper(s, locked, 2, 2).
Step 3: Third Call
- Call: canBeValidHelper(s, locked, 2, 2)
- index = 2, balance = 2.
- locked[2] = '0' (unlocked).
Try both options:
Change s[2] to '(' (increase balance).
Next Call: canBeValidHelper(s, locked, 3, 3).
Change s[2] to ')' (decrease balance).
Next Call: canBeValidHelper(s, locked, 3, 1).
Branch 1: Fourth Call (Option 1 - s[2] = '(')
- Call: canBeValidHelper(s, locked, 3, 3)
- index = 3, balance = 3.
- locked[3] = '0' (unlocked).
Try both options:
Change s[3] to '(' (increase balance).
Next Call: canBeValidHelper(s, locked, 4, 4).
Change s[3] to ')' (decrease balance).
Next Call: canBeValidHelper(s, locked, 4, 2).
Branch 1.1: Fifth Call (Option 1 - s[3] = '(')
- Call: canBeValidHelper(s, locked, 4, 4)
- index = 4, balance = 4.
- locked[4] = '1', s[4] = ')': Decrease balance to 3.
- Next Call: canBeValidHelper(s, locked, 5, 3).
Branch 1.1.1: Sixth Call
- Call: canBeValidHelper(s, locked, 5, 3)
- index = 5, balance = 3.
- locked[5] = '0' (unlocked).
Try both options:
Change s[5] to '(' (increase balance).
Next Call: canBeValidHelper(s, locked, 6, 4).
Change s[5] to ')' (decrease balance).
Next Call: canBeValidHelper(s, locked, 6, 2).
Branch 1.1.1.1: Seventh Call (Option 1 - s[5] = '(')
- Call: canBeValidHelper(s, locked, 6, 4)
- index = 6, balance = 4.
- locked[6] = '1', s[6] = '(': Increase balance to 5.
- Next Call: canBeValidHelper(s, locked, 7, 5).
Branch 1.1.1.1.1: Eighth Call
- Call: canBeValidHelper(s, locked, 7, 5)
- index = 7, balance = 5.
- locked[7] = '0' (unlocked).
Try both options:
Change s[7] to '(' (increase balance).
Next Call: canBeValidHelper(s, locked, 8, 6).
Change s[7] to ')' (decrease balance).
Next Call: canBeValidHelper(s, locked, 8, 4).
Branch 1.1.1.1.1.1: Ninth Call (Option 1 - s[7] = '(')
- Call: canBeValidHelper(s, locked, 8, 6)
- index = 8, balance = 6.
- Base case reached.
- balance != 0, so return false.
Branch 1.1.1.1.1.2: Ninth Call (Option 2 - s[7] = ')')
- Call: canBeValidHelper(s, locked, 8, 4)
- index = 8, balance = 4.
- Base case reached.
- balance != 0, so return false.
Backtracking to Branch 1.1.1.1 (Option 2 - s[5] = ')')
- Similar logic applies, and the result will be false for all branches as the balances will never become 0 at the base case.
Final Answer
- After exploring all possible branches, no valid configuration is found.
- Output: false.
Brute Force Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
bool canBeValid(string s, string locked) {
// If the length of the string is odd, it's impossible to make it valid
if (s.length() % 2 != 0) return false;
// Call helper function to check if the string can be valid
return canBeValidHelper(s, locked, 0, 0);
}
private:
bool canBeValidHelper(string& s, string& locked, int index, int balance) {
// Base case: if we reach the end of the string
if (index == s.length()) {
return balance == 0; // Valid only if balance is zero
}
// If balance is negative, it's already invalid
if (balance < 0) {
return false;
}
// If the current character is locked, we cannot change it
if (locked[index] == '1') {
// If the character is '(', increase balance
if (s[index] == '(') {
return canBeValidHelper(s, locked, index + 1, balance + 1);
} else {
// If the character is ')', decrease balance
return canBeValidHelper(s, locked, index + 1, balance - 1);
}
} else {
// If the current character is not locked, try both '(' and ')'
return canBeValidHelper(s, locked, index + 1, balance + 1) ||
canBeValidHelper(s, locked, index + 1, balance - 1);
}
}
};2. Java Try on Compiler
class Solution {
public boolean canBeValid(String s, String locked) {
// If the length of the string is odd, it's impossible to make it valid
if (s.length() % 2 != 0) return false;
// Call helper function to check if the string can be valid
return canBeValidHelper(s.toCharArray(), locked.toCharArray(), 0, 0);
}
private boolean canBeValidHelper(char[] s, char[] locked, int index, int balance) {
// Base case: if we reach the end of the string
if (index == s.length) {
return balance == 0; // Valid only if balance is zero
}
// If balance is negative, it's already invalid
if (balance < 0) {
return false;
}
// If the current character is locked, we cannot change it
if (locked[index] == '1') {
// If the character is '(', increase balance
if (s[index] == '(') {
return canBeValidHelper(s, locked, index + 1, balance + 1);
} else {
// If the character is ')', decrease balance
return canBeValidHelper(s, locked, index + 1, balance - 1);
}
} else {
// If the current character is not locked, try both '(' and ')'
return canBeValidHelper(s, locked, index + 1, balance + 1) ||
canBeValidHelper(s, locked, index + 1, balance - 1);
}
}
}
3. Python Try on Compiler
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
# If the length of the string is odd, it's impossible to make it valid
if len(s) % 2 != 0:
return False
# Call helper function to check if the string can be valid
return self.canBeValidHelper(list(s), list(locked), 0, 0)
def canBeValidHelper(self, s, locked, index, balance):
# Base case: if we reach the end of the string
if index == len(s):
return balance == 0 # Valid only if balance is zero
# If balance is negative, it's already invalid
if balance < 0:
return False
# If the current character is locked, we cannot change it
if locked[index] == '1':
# If the character is '(', increase balance
if s[index] == '(':
return self.canBeValidHelper(s, locked, index + 1, balance + 1)
else:
# If the character is ')', decrease balance
return self.canBeValidHelper(s, locked, index + 1, balance - 1)
else:
# If the current character is not locked, try both '(' and ')'
return (self.canBeValidHelper(s, locked, index + 1, balance + 1) or
self.canBeValidHelper(s, locked, index + 1, balance - 1))
4. JavaScript Try on Compiler
/**
* @param {string} s
* @param {string} locked
* @return {boolean}
*/
var canBeValid = function(s, locked) {
// If the length of the string is odd, it's impossible to make it valid
if (s.length % 2 !== 0) return false;
// Helper function to check if the string can be valid
function canBeValidHelper(s, locked, index, balance) {
// Base case: if we reach the end of the string
if (index === s.length) {
return balance === 0; // Valid only if balance is zero
}
// If balance is negative, it's already invalid
if (balance < 0) {
return false;
}
// If the current character is locked, we cannot change it
if (locked[index] === "1") {
// If the character is '(', increase balance
if (s[index] === "(") {
return canBeValidHelper(s, locked, index + 1, balance + 1);
} else {
// If the character is ')', decrease balance
return canBeValidHelper(s, locked, index + 1, balance - 1);
}
} else {
// If the current character is not locked, try both '(' and ')'
return canBeValidHelper(s, locked, index + 1, balance + 1) ||
canBeValidHelper(s, locked, index + 1, balance - 1);
}
}
// Call the helper function to check if the string can be valid
return canBeValidHelper(s.split(""), locked.split(""), 0, 0);
};
Time Complexity: O(2^n)
Recursive Calls:
- In the worst case, for every character in the string s, there are two recursive calls because, for unlocked characters (locked[index] == '0'), the algorithm tries both possibilities: setting the character to '(' or ')'.
- The recursion tree height is equal to the length of the string, n.
- The number of nodes in the recursion tree grows exponentially in the worst case, leading to a total of O(2^n) recursive calls.
Character Comparisons: At each recursive call, a constant amount of work (comparison and decision-making) is performed, which does not affect the overall exponential growth.
Worst-Case Time Complexity: O(2^n).
Space Complexity: O(n)
Auxiliary Space (Stack Space): The extra space required by an algorithm other than the input space.
- The recursion stack depth is equal to the length of the string, n, as there is one recursive call per index.
- Each recursive call requires O(1) space for storing local variables like index and balance.
Auxiliary Space: O(n).
Input Storage:
- The function converts the input strings s and locked into character arrays.
- This requires additional space proportional to the input size.
Input Storage: O(n).
Total Space Complexity: O(n) (for recursion stack and input storage).
The brute force approach led us to an exponential time complexity, which is too slow for higher constraints.
The problem statement involves pen and paper work rather than the Brute Force Approach, we need to build intuitions from the examples and figure out the optimal approach.
Better Approach
Intuition
Before moving to the optimal algorithm we must understand what a valid parentheses means.
A valid parentheses means for every opening bracket at index i , there must be a closing bracket with index j where, i<j.
This means for a string of parentheses to be valid there must be even no of parentheses present.
Our first observation is , the length of the string should be even
In the problem statement, apart from the string s, we have a string locked with 0s and 1s, each bracket has a rule: If the bracket is locked (locked[i] = '1'), we cannot change it. It must stay as it is '(' or ')'. If the bracket is unlocked (locked[i] = '0'), you can change it to either '(' or ')'.
Let's take this example itself where
Input: s = "))()))",
locked = "010100"
In this example string s is not valid, but can we make it a valid string ? Let's see how we can perform it.
The bold characters in the string s= "))()))" can be altered or left as it is.
In the naked eye, we can see that s[0] can be modified to '(' and s[4] can be modified to '(' to make the string s valid.
Did you notice that s[2] character was not altered !!
For better understanding lets initialize another string of s="))()))" to s' = "*)*)**".
Here, '*' means that particular character can be either set to '(' or ')' based on our logic. '*' character is placed wherever the locked[i]==0.
Why are we initializing another string ?
We constructed another string to clearly visualize ,on how we can alter the string s' to declare it valid or not!!
Since, we are familiar with the "Valid Parentheses" question, we must be getting intuitions of using a stack ,since this question too involves checking if a string can be made a valid parentheses or not.
Alright, we got to know that we can use a stack to solve this question, but what logic to follow?
Let's take an example
s'= "* ( ) )"
So, while traversing, we maintain a stack to store the occurrence of the opening parentheses.
When we encounter the '(' at s[1] we will push to the stack.
When we encounter the ')' at s[2] we will pop from the stack. But, we could have also checked that the * is also there which can be converted to ')'. Here, we greedily tried to map the ')' with the '(' .
In other words, we are saying that the * is for a backup purpose i.e. if at end the parentheses need balancing then we may use it !!
Where to store the index of * ?? In a stack again !!
Why we use another stack to store '*' indices ?
We store the * indices in a stack to let us know the earliest occurred * which will help us in mapping it with the imbalanced part.
Let's understand with a small example !
Suppose the string s' = "*)()",
We will be having two stacks, stack1 to store the indices of the opening parentheses and stack2 to store the indices of *.
- when we encounter the * we will push 0 on to the stack2.
- Next, when we encounter ')' , first we check if there is any '(' in stack1, if not we will check the stack2, if the stack2 is not empty this means the '*' can be altered to '('.
Which means we will pop out the * from stack2.
And so on.
But what if the s' = "(*))".
at index 2,
our stack1 will contain a '(' and stack2 will contain '*'. At index 2, we encounter a ')'.
Shall we pop out the * ?
No, because if we think greedily, we have already a '(' in stack1. So, we will pop '(' from the stack1.
stack2 store the indices of the *s.
From this example we figured out that
if we encounter a ')' and our stack1 is empty and stack2 is not empty, we will pop from the stack2.
while, if stack1 was not empty and stack2 was also not empty, we will pop from stack1.
If, both the stacks are empty, then we cannot make the string as valid. This is because there are no *s or '(' to a ')' previously, hence it can't be made a valid parentheses.
Let's take another example
If s' = "((**",
the stack1 will contain the indices of two '('.
the stack2 will contain the indices of two '*'.
We didn't encounter any ')'. But there are 2*s present in the stack2 and 2'('s in the stack1.
All of the '(' occurred before the two *s, then we can declare s' a valid parentheses.
We are saying that for every '('s we will pop the '*'s present in the stack conditioned that the '('s appears before each *s.
Are we missing something?
What if the string has only '*' present in it i.e the stack2 is not empty?
We will just check if the size of stack2 is even or not. Even size signifies that we can form pairs of '(' and ')' to make it valid.
Let's now see how we can code it up !!
We won't be declaring another string s' since it was only for our visualization. The index of '*'s here represents,that particular index in s can be altered .
Approach
Step 1: Initialize variables:
- Get the length of the string, stringLength.
- If stringLength is odd, return false (a valid string must have an even length).
- Create two stacks: openIndices to track indices of locked open parentheses '('.
unlockedIndices to track indices of unlocked characters.
Step 2: Traverse the string: For each character at index i in the string:
- If the character is unlocked (locked[i] == '0'), push i to unlockedIndices.
- Else if the character is '(', push i to openIndices.
- Else if the character is ')':
If openIndices is not empty, pop the top element (use the locked open parenthesis).
Else if unlockedIndices is not empty, pop the top element (use the unlocked character as an open parenthesis).
Else, return false (no valid match for this closing parenthesis).
Step 3: Match remaining open parentheses:
While both openIndices and unlockedIndices are not empty:
- If the index of the top element in openIndices is less than the top element in unlockedIndices:
Pop one element from each stack (use the unlocked character as a closing parenthesis).
Otherwise, break the loop.
Step 4: Final check:
If openIndices is empty:
- Check if the remaining size of unlockedIndices is even (unlocked characters can be paired to form valid parentheses).
- Return true if it is even, false otherwise.
If openIndices is not empty, return false.
Step 5: Return the result: Return true if all checks pass and the string can be valid.
openIndices stores the indices of '('.
unlockedIndices stores the indices of '*'s.
Dry-Run
Input:
- s = "(()))(()"
- locked = "11000110"
Step 1: Initial Setup
- stringLength = 8 (length of s).
- Check if stringLength % 2 == 1: Since 8 % 2 == 0, proceed.
- Initialize two stacks: openIndices = [] (tracks indices of open parentheses '(').
unlockedIndices = [] (tracks indices of unlocked parentheses '0').
Step 2: Left-to-Right Traversal
Index 0:
- s[0] = '(', locked[0] = '1'.
- Push 0 to openIndices.
- State: openIndices = [0], unlockedIndices = [].
Index 1:
- s[1] = '(', locked[1] = '1'.
- Push 1 to openIndices.
- State: openIndices = [0, 1], unlockedIndices = [].
Index 2:
- s[2] = ')', locked[2] = '0'.
- Push 2 to unlockedIndices.
- State: openIndices = [0, 1], unlockedIndices = [2].
Index 3:
- s[3] = ')', locked[3] = '0'.
- Push 3 to unlockedIndices.
- State: openIndices = [0, 1], unlockedIndices = [2, 3].
Index 4:
- s[4] = ')', locked[4] = '1'.
- No matching open parenthesis in openIndices, so pop from unlockedIndices.
- State: openIndices = [0, 1], unlockedIndices = [2].
Index 5:
- s[5] = '(', locked[5] = '0'.
- Push 5 to unlockedIndices.
- State: openIndices = [0, 1], unlockedIndices = [2, 5].
Index 6:
- s[6] = '(', locked[6] = '1'.
- Push 6 to openIndices.
- State: openIndices = [0, 1, 6], unlockedIndices = [2, 5].
Index 7:
- s[7] = ')', locked[7] = '0'.
- Pop from openIndices (match '(' at index 6).
- State: openIndices = [0, 1], unlockedIndices = [2, 5].
Step 3: Matching Remaining Parentheses
Match remaining openIndices with unlockedIndices:
First Match:
- Pop 1 from openIndices and 5 from unlockedIndices.
- State: openIndices = [0], unlockedIndices = [2].
- Second Match:Pop 0 from openIndices and 2 from unlockedIndices.
State: openIndices = [], unlockedIndices = [].
Step 4: Final Check
At this point, both openIndices and unlockedIndices are empty. However, the string itself is invalid:
After all adjustments, s still contains unmatched parentheses (more closing than opening overall). Thus, the string cannot be valid.
Output Result: false.
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
bool canBeValid(string s, string locked) {
int stringLength = s.length();
// If the string length is odd, return false
if (stringLength % 2 == 1) {
return false;
}
stack<int> openIndices, unlockedIndices;
// Traverse the string
for (int i = 0; i < stringLength; i++) {
// If the current character is unlocked, push its index to unlockedIndices
if (locked[i] == '0') {
unlockedIndices.push(i);
}
// If it's an open parenthesis, push its index to openIndices
else if (s[i] == '(') {
openIndices.push(i);
}
// If it's a close parenthesis
else if (s[i] == ')') {
// If there's a matching open parenthesis, pop from openIndices
if (!openIndices.empty()) {
openIndices.pop();
}
// Otherwise, if there's an unlocked parenthesis, pop from unlockedIndices
else if (!unlockedIndices.empty()) {
unlockedIndices.pop();
}
// If neither, return false
else {
return false;
}
}
}
// Match remaining open parentheses with unlocked parentheses
while (!openIndices.empty() && !unlockedIndices.empty() &&
openIndices.top() < unlockedIndices.top()) {
openIndices.pop();
unlockedIndices.pop();
}
// Final check: if there are unmatched open parentheses and unlocked parentheses
if (openIndices.empty() && !unlockedIndices.empty()) {
// Return true if unlockedIndices size is even
return unlockedIndices.size() % 2 == 0;
}
// Return true if there are no unmatched open parentheses
return openIndices.empty();
}
};2. Java Try on Compiler
class Solution {
// Method to check if the string can be valid
public boolean canBeValid(String s, String locked) {
// Get the length of the string
int stringLength = s.length();
// If the string length is odd, return false
if (stringLength % 2 == 1) {
return false;
}
// Stack to track the indices of open parentheses
Stack<Integer> openIndices = new Stack<>();
// Stack to track the indices of unlocked parentheses
Stack<Integer> unlockedIndices = new Stack<>();
// Traverse the string
for (int i = 0; i < stringLength; i++) {
// If the current character is unlocked, push its index to unlockedIndices
if (locked.charAt(i) == '0') {
unlockedIndices.push(i);
}
// If it's an open parenthesis, push its index to openIndices
else if (s.charAt(i) == '(') {
openIndices.push(i);
}
// If it's a close parenthesis
else if (s.charAt(i) == ')') {
// If there's a matching open parenthesis, pop from openIndices
if (!openIndices.isEmpty()) {
openIndices.pop();
}
// Otherwise, if there's an unlocked parenthesis, pop from unlockedIndices
else if (!unlockedIndices.isEmpty()) {
unlockedIndices.pop();
}
// If neither, return false
else {
return false;
}
}
}
// Match remaining open parentheses with unlocked parentheses
while (!openIndices.isEmpty() && !unlockedIndices.isEmpty() &&
openIndices.peek() < unlockedIndices.peek()) {
openIndices.pop();
unlockedIndices.pop();
}
// Final check: if there are unmatched open parentheses and unlocked parentheses
if (openIndices.isEmpty() && !unlockedIndices.isEmpty()) {
// Return true if unlockedIndices size is even
return unlockedIndices.size() % 2 == 0;
}
// Return true if there are no unmatched open parentheses
return openIndices.isEmpty();
}
}3. Python Try on Compiler
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
stringLength = len(s)
# If the string length is odd, return false
if stringLength % 2 == 1:
return False
openIndices, unlockedIndices = [], []
# Traverse the string
for i in range(stringLength):
# If the current character is unlocked, push its index to unlockedIndices
if locked[i] == '0':
unlockedIndices.append(i)
elif s[i] == '(':
openIndices.append(i)
elif s[i] == ')':
# If there's a matching open parenthesis, pop from openIndices
if openIndices:
openIndices.pop()
# Otherwise, if there's an unlocked parenthesis, pop from unlockedIndices
elif unlockedIndices:
unlockedIndices.pop()
else:
return False
# Match remaining open parentheses with unlocked parentheses
while openIndices and unlockedIndices and openIndices[-1] < unlockedIndices[-1]:
openIndices.pop()
unlockedIndices.pop()
# Final check: if there are unmatched open parentheses and unlocked parentheses
if not openIndices and unlockedIndices:
return len(unlockedIndices) % 2 == 0
# Return true if there are no unmatched open parentheses
return not openIndices
4. JavaScript Try on Compiler
var canBeValid = function(s, locked) {
const stringLength = s.length;
// If the string length is odd, return false
if (stringLength % 2 !== 0) return false;
const openIndices = [];
const unlockedIndices = [];
// Traverse the string
for (let i = 0; i < stringLength; i++) {
// If the current character is unlocked, push its index to unlockedIndices
if (locked.charAt(i) === '0') {
unlockedIndices.push(i);
}
// If it's an open parenthesis, push its index to openIndices
else if (s.charAt(i) === '(') {
openIndices.push(i);
}
// If it's a close parenthesis
else if (s.charAt(i) === ')') {
// If there's a matching open parenthesis, pop from openIndices
if (openIndices.length > 0) {
openIndices.pop();
}
// Otherwise, if there's an unlocked parenthesis, pop from unlockedIndices
else if (unlockedIndices.length > 0) {
unlockedIndices.pop();
}
// If neither, return false
else {
return false;
}
}
}
// Match remaining open parentheses with unlocked parentheses
while (openIndices.length > 0 && unlockedIndices.length > 0 &&
openIndices[openIndices.length - 1] < unlockedIndices[unlockedIndices.length - 1]) {
openIndices.pop();
unlockedIndices.pop();
}
// Final check: if there are unmatched open parentheses and unlocked parentheses
if (openIndices.length === 0 && unlockedIndices.length > 0) {
return unlockedIndices.length % 2 === 0;
}
// Return true if there are no unmatched open parentheses
return openIndices.length === 0;
};Time Complexity: O(n)
Traversing the string: The algorithm iterates over the string s once. For each character in the string, it performs constant-time operations like checking if it's locked or pushing/popping from stacks. The traversal has a time complexity of O(n) where n is the length of the string.
Stack operations: Stack operations (push, pop, and peek) are all O(1) operations, meaning they do not contribute additional complexity beyond the traversal.
Matching remaining open parentheses: After the traversal, there is a second phase where unmatched parentheses are handled using stacks. In the worst case, this also requires iterating through the stacks once. The worst-case time complexity of this phase is O(n) since at most, there can be n/2 open and unlocked parentheses remaining.
Thus, the overall time complexity of the algorithm is: O(n)
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm that is not part of the input. This includes the space required by any data structures like stacks.
Stacks: The algorithm uses two stacks:
- openIndices stores the indices of the open parentheses ('(').
- unlockedIndices stores the indices of the unlocked parentheses.
In the worst case, each of these stacks can hold up to n/2 elements, meaning the total space used by the stacks is O(n).
Other variables: There are only a few integer variables (stringLength and loop variables), which use O(1) space.
Thus, the auxiliary space complexity is: O(n)
Total Space Complexity:
Total space complexity refers to the sum of the space used by the input (the string and the locked string) plus the auxiliary space.
- Input space: The strings s and locked both take O(n) space because the input strings are of length n.
- Auxiliary space: As mentioned earlier, the algorithm uses O(n) space for the stacks.
Thus, the total space complexity is: O(n).
In most of the interviews, even if we crack an optimal algorithm, we will often be asked whether we can optimize it further with constant space. This will show how good is our understanding skills.
Is there a better approach than the stack one ?? Is it possible to generate the output with constant space !!
Optimal Approach
Intuition
The answer we want to figure out is involved only in counting the opening and closing parentheses. But, we also have a string locked[] stating that few of the parentheses can be altered only if locked[i]='0'. So we will maintain two variables one is open and another is close. But how are we gonna track the *s ?
If you clearly observe that the *s could be either altered to a '(' or ')'. We know that for a string of parentheses to be valid, we must be able to match each ( with a corresponding ) in a balanced manner: For every (, there must be a ) later in the string to balance it. If we traverse the string and encounter a ), we must have already seen a ( earlier to match it.
We used one pass that is from left to right in the earlier approach because as we move left to right, we want to check if there is any point where there are more closing parentheses ) than opening parentheses (. If we encounter this situation, it immediately indicates that the string cannot be balanced at that point.
At each point, we want to track how many opening parentheses we have encountered ((), and how many closing parentheses ) have been seen, if we encounter a '(' or locked[i]=='0', we will increment the open by 1 or else close by 1.
Why We Increase the open count, When We Encounter locked[i] == '0' or ( in Left-to-Right Pass ?
When locked[i] == '0': This means the parenthesis at index i is unlocked, and we are allowed to change it. To balance the parentheses:If we encounter an unlocked parenthesis, we assume the best case scenario: we treat it as an open parenthesis ( (this helps balance the parentheses). Since we can convert it into either ( or ), we choose to increase the count of opening parentheses.
When s[i] == '(': If the character is already an opening parenthesis (, it naturally adds to the count of opening parentheses. We increment the open count because we need a matching closing parenthesis later.
But are we missing something !!
Did you notice that the indices that we were storing in the stack appeared to be in reverse order if viewed from the top of the stack?? It gives us the hint to traverse the s' string in reversed order.
Back to basics, in the previous approach, we tried to balance each pair. So, we will have a right to left pass as well.
The reason we perform this pass is to check that, after traversing from the left, the remaining unmatched opening parentheses '(' (which are still unbalanced after the first pass) can still be matched with closing parentheses ')' that come later.
If at any point in the right-to-left pass, the number of closing parentheses ) exceeds the number of open parentheses (, it means the string cannot be balanced and is invalid. We will increment the open by 1 if locked[i]=='0' or the character of s' is ')' else we will increase close by 1.
Why We Increase the open count, When We Encounter locked[i] == '0' or ) in Right-to-Left Pass:
When locked[i] == '0': This again means the parenthesis at index i is unlocked, and we can change it. In this case, we assume that we can change it to a closing parenthesis ) to help balance the parentheses. So, we treat it as if it's a closing parenthesis ) and increase the open count to track how many closing parentheses are available.
When s[i] == ')': If the character is already a closing parenthesis ), we increment the open count because this represents a valid closing parenthesis that can be paired with an opening parenthesis (.
If in any of the parsing, if the value of close is greater than the value of open, we can say that the valid pairing cannot happen and hence we return false.
Approach
Initialize variables:
- close = 0, open = 0 to track counts of closing and opening parentheses.
- n = s.length() to get the length of the string.
Check if the length of the string is odd:
- If n % 2 != 0, return false because a valid string must have an even number of characters.
Left to Right Traversal: For i from 0 to n-1:
- If locked[i] == '0' (unlocked parenthesis) or s[i] == '(' (opening parenthesis): Increment open by 1.
- Else (locked closing parenthesis )): Increment close by 1.
- If at any point, close > open: Return false (invalid string).
Right to Left Traversal: Reset open = 0 and close = 0.
For i from n-1 to 0:
- If locked[i] == '0' (unlocked parenthesis) or s[i] == ')' (closing parenthesis): Increment open by 1.
- Else (locked opening parenthesis (): Increment close by 1.
- If at any point, close > open: Return false (invalid string).
Final Check: If both traversals complete without returning false: Return true (string can be valid).
Dry-Run
Input:
- s = "(()))(()"
- locked = "11000110"
Output: False
Dry Run: Input Details
- s = "(()))(()"
- locked = "11000110"
Execution Steps
Step 1: Check Length
- Length of s is n = 8.
- Since n % 2 == 0, we proceed.
Step 2: Left-to-Right Traversal
- Initialize open = 0, close = 0.
- Iterate through the string s from left to right:
Index 0: s[0] = '(', locked[0] = '1'.
- Add to open. Now, open = 1.
Index 1: s[1] = '(', locked[1] = '1'.
- Add to open. Now, open = 2.
Index 2: s[2] = ')', locked[2] = '0'.
- Add to open since it is unlocked. Now, open = 3.
Index 3: s[3] = ')', locked[3] = '0'.
- Add to open since it is unlocked. Now, open = 4.
Index 4: s[4] = ')', locked[4] = '1'.
- Add to close. Now, close = 1.
Index 5: s[5] = '(', locked[5] = '0'.
- Add to open since it is unlocked. Now, open = 5.
Index 6: s[6] = '(', locked[6] = '1'.
- Add to open. Now, open = 6.
Index 7: s[7] = ')', locked[7] = '0'.
- Add to open since it is unlocked. Now, open = 7.
- During traversal, close never exceeds open. Continue to the next traversal.
- Reset open = 0, close = 0.
Step 3: Right-to-Left Traversal
Iterate through the string s from right to left:
Index 7: s[7] = ')', locked[7] = '0'.
- Add to open since it is unlocked. Now, open = 1.
Index 6: s[6] = '(', locked[6] = '1'.
- Add to close. Now, close = 1.
Index 5: s[5] = '(', locked[5] = '0'.
- Add to open since it is unlocked. Now, open = 2.
Index 4: s[4] = ')', locked[4] = '1'.
- Add to open. Now, open = 3.
Index 3: s[3] = ')', locked[3] = '0'.
- Add to open since it is unlocked. Now, open = 4.
Index 2: s[2] = ')', locked[2] = '0'.
- Add to open since it is unlocked. Now, open = 5.
Index 1: s[1] = '(', locked[1] = '1'.
- Add to close. Now, close = 2.
Index 0: s[0] = '(', locked[0] = '1'.
- Add to close. Now, close = 3.
- At Index 0, close > open (3 > 2).
- Return false.
Final Output
- Left-to-right valid? Yes.
- Right-to-left valid? No.
- Result: false.
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
bool canBeValid(string s, string locked) {
int close = 0;
int open = 0;
int n = s.length();
// If the string length is odd, return false
if (n % 2 != 0)
return false;
// Traverse the string from left to right
for (int i = 0; i < n; i++) {
// If the current character is unlocked or it's an open parenthesis
if (locked[i] == '0' || s[i] == '(')
open++;
else
close++;
// If there are more close parentheses than open, return false
if (close > open)
return false;
}
// Reset open and close counts
open = 0;
close = 0;
// Traverse the string from right to left
for (int i = n - 1; i >= 0; i--) {
// If the current character is unlocked or it's a close parenthesis
if (locked[i] == '0' || s[i] == ')')
open++;
else
close++;
// If there are more close parentheses than open, return false
if (close > open)
return false;
}
// Return true if no invalid configuration found
return true;
}
};
2. Java Try on Compiler
class Solution {
// Method to check if the string can be valid
public boolean canBeValid(String s, String locked) {
// Get the length of the string
int close = 0;
int open = 0;
int n = s.length();
// If the string length is odd, return false
if (n % 2 != 0)
return false;
// Traverse the string from left to right
for (int i = 0; i < n; i++) {
// If the current character is unlocked or it's an open parenthesis
if (locked.charAt(i) == '0' || s.charAt(i) == '(')
open++;
else
close++;
// If there are more close parentheses than open, return false
if (close > open)
return false;
}
// Reset open and close counts
open = 0;
close = 0;
// Traverse the string from right to left
for (int i = n - 1; i >= 0; i--) {
// If the current character is unlocked or it's a close parenthesis
if (locked.charAt(i) == '0' || s.charAt(i) == ')')
open++;
else
close++;
// If there are more close parentheses than open, return false
if (close > open)
return false;
}
// Return true if no invalid configuration found
return true;
}
}3. Python Try on Compiler
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
close = 0
open = 0
n = len(s)
# If the string length is odd, return false
if n % 2 != 0:
return False
# Traverse the string from left to right
for i in range(n):
# If the current character is unlocked or it's an open parenthesis
if locked[i] == '0' or s[i] == '(':
open += 1
else:
close += 1
# If there are more close parentheses than open, return false
if close > open:
return False
# Reset open and close counts
open = 0
close = 0
# Traverse the string from right to left
for i in range(n - 1, -1, -1):
# If the current character is unlocked or it's a close parenthesis
if locked[i] == '0' or s[i] == ')':
open += 1
else:
close += 1
# If there are more close parentheses than open, return false
if close > open:
return False
# Return true if no invalid configuration found
return True4. JavaScript Try on Compiler
var canBeValid = function(s, locked) {
let close = 0;
let open = 0;
const n = s.length;
// If the string length is odd, return false
if (n % 2 !== 0) return false;
// Traverse the string from left to right
for (let i = 0; i < n; i++) {
// If the current character is unlocked or it's an open parenthesis
if (locked[i] === '0' || s[i] === '(')
open++;
else
close++;
// If there are more close parentheses than open, return false
if (close > open) return false;
}
// Reset open and close counts
open = 0;
close = 0;
// Traverse the string from right to left
for (let i = n - 1; i >= 0; i--) {
// If the current character is unlocked or it's a close parenthesis
if (locked[i] === '0' || s[i] === ')')
open++;
else
close++;
// If there are more close parentheses than open, return false
if (close > open) return false;
}
// Return true if no invalid configuration found
return true;
};Time Complexity: O(n)
First loop (left-to-right):
This loop iterates over each character in the string s (and locked) exactly once.
For each character, the program performs constant-time operations (checking characters and updating counters).
Time complexity of this loop: O(n), where n is the length of the string s.
Second loop (right-to-left):
Similar to the first loop, this loop also iterates over each character in the string exactly once.
Again, constant-time operations are performed for each character.
Time complexity of this loop: O(n).
Final check: The final check for returning the result is just a comparison, which is a constant-time operation: O(1).
Total Time Complexity:
The total time complexity is the sum of the two loops and the final check: O(n) + O(n) + O(1) = O(n).
Thus, the time complexity is O(n), where n is the length of the string s.
Space Complexity: O(1)
Auxiliary Space Complexity:
- The solution does not use any additional data structures (like stacks or arrays) that grow with the size of the input. It only uses a few integer variables (close, open, n) to keep track of counts and indices.
- The space used is constant because no extra space is allocated that depends on the input size.
Auxiliary Space Complexity: O(1) (constant space).
Total Space Complexity:
- The space used for the input strings is O(n).
- The auxiliary space is O(1) (since no other significant data structures are used).
Thus, the total space complexity is O(n) due to the input storage.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
- For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.
A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.
Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.
A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:
- It is the empty string, or
- It can be written as AB (A concatenated with B), where A and B are VPS's, or
- It can be written as (A), where A is a VPS.
We can similarly define the nesting depth depth(S) of any VPS S as follows:
- depth("") = 0
- depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
- depth("(" + A + ")") = 1 + depth(A), where A is a VPS.
For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.
Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).
Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.
Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.