# 12.01.2025 [2116. Check if a Parentheses String Can Be Valid]
Balance parenthesis with wildcards #medium
12.01.2025
2116. Check if a Parentheses String Can Be Valid medium blog post substack youtube deep-dive
Join me on Telegram
Problem TLDR
Balance parenthesis with wildcards #medium
Intuition
Didn't solve it without a hint.
Some examples to observe the problem:
// 100000
// (((()(
// 000111
// ()((()
// 101111 f b
// ((()))
// * 0 1
// * 1 2
The corner cases that can't be balanced:
odd string length
locked unbalanced open brace (which is why we have to check the reversed order too)
The hint is: greedy solution just works, consider unlocked positions as wildcards, balance otherwise and check corner cases.
Approach
separate counters
wildcards
andbalance
can just be a singlebalance
variable, ifwildcards + balance >= 0
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
fun canBeValid(s: String, locked: String, o: Char = '('): Boolean {
if (s.length % 2 > 0) return false; var b = 0
for (i in s.indices)
if (s[i] == o || locked[i] == '0') b++
else if (--b < 0) return false
return o == ')' || canBeValid(s.reversed(), locked.reversed(), ')')
}
pub fn can_be_valid(s: String, locked: String) -> bool {
if s.len() % 2 > 0 { return false }
let (mut b, mut o, s) = ([0, 0], [b'(', b')'], s.as_bytes());
for i in 0..s.len() { for j in 0..2 {
let i = if j > 0 { s.len() - 1 - i } else { i };
if s[i] == o[j] || locked.as_bytes()[i] == b'0' { b[j] += 1 }
else { b[j] -= 1; if b[j] < 0 { return false }}
}}; true
}
bool canBeValid(string s, string locked) {
if (s.size() % 2 > 0) return 0;
int b[2] = {0}, o[2] = {'(', ')'};
for (int i = 0; i < s.size(); ++i) for (int j = 0; j < 2; ++j) {
int k = j ? s.size() - 1 - i : i;
if (s[k] == o[j] || locked[k] == '0') ++b[j];
else if (--b[j] < 0) return 0;
} return 1;
}