First, I checked if the length of the string s is odd. If it is, then I return False in that case.
Next, I realized that balancing the parentheses is a good way to solve the problem. In the first pass, I traversed the string from left to right. I used two counters: one to track the possible number of opening parentheses open_possible, including the flexibility from locked[i] == '0', and another to track the number of fixed closing parentheses close_possible. As I went through the string, I incremented open_possible for either an opening parenthesis or an unlocked position (locked[i] == '0) that could be converted into one. Also, I incremented close_possible for each fixed closing parenthesis. At any point, if close_possible exceeded open_possible, it meant there were too many closing parentheses to ever balance the string, and I returned False.
After ensuring that the string could be balanced from left to right, I reversed the process. In the second pass, I traversed the string from right to left. This time, I used the same two counters but swapped their roles: I incremented close_possible for closing parentheses or flexible positions and open_possible for fixed opening parentheses. Similarly, if at any point open_possible exceeded close_possible, I returned False.
Finally, if both passes completed without any imbalance, I returned True.
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
if len(s) % 2 != 0:
return False
open_possible, close_possible = 0, 0
for i in range(len(s)):
if locked[i] == '0' or s[i] == '(':
open_possible += 1
else:
close_possible += 1
if close_possible > open_possible:
return False
open_possible, close_possible = 0, 0
for i in range(len(s) - 1, -1, -1):
if locked[i] == '0' or s[i] == ')':
close_possible += 1
else:
open_possible += 1
if open_possible > close_possible:
return False
return True- Time: O(n), the string is iterated through twice.
- Space: O(1)
