Valid Parenthesis String
Problem
Given a string s containing only '(', ')' and '*', return true if s is valid. '*' can be treated as '(', ')', or the empty string.
s = "(*))"truedef check_valid_string(s):
lo = hi = 0
for c in s:
lo += 1 if c == '(' else -1
hi += 1 if c != ')' else -1
if hi < 0:
return False
lo = max(lo, 0)
return lo == 0function checkValidString(s) {
let lo = 0, hi = 0;
for (const c of s) {
lo += c === '(' ? 1 : -1;
hi += c !== ')' ? 1 : -1;
if (hi < 0) return false;
if (lo < 0) lo = 0;
}
return lo === 0;
}class Solution {
public boolean checkValidString(String s) {
int lo = 0, hi = 0;
for (char c : s.toCharArray()) {
lo += c == '(' ? 1 : -1;
hi += c != ')' ? 1 : -1;
if (hi < 0) return false;
lo = Math.max(lo, 0);
}
return lo == 0;
}
}bool checkValidString(string s) {
int lo = 0, hi = 0;
for (char c : s) {
lo += c == '(' ? 1 : -1;
hi += c != ')' ? 1 : -1;
if (hi < 0) return false;
lo = max(lo, 0);
}
return lo == 0;
}Explanation
The wildcard * can be a (, a ), or nothing, which makes brute force explode. The clever fix is to track a range of how many open parentheses we could have at each step, using two counters lo and hi.
hi is the most open parens possible (treat every * as (), and lo is the fewest (treat every * as )). On ( both go up; on ) both go down; on *, hi goes up while lo goes down.
Two guards make it correct. If hi ever drops below 0, even the most generous reading has too many closers, so we fail immediately. And we clamp lo to never go below 0, because you can't have negative open parens — extra * simply act as empty.
Example: s = "(*))". After (: lo=1, hi=1. After *: lo=0, hi=2. After ): lo=0, hi=1. After ): lo=0, hi=0. hi never went negative and lo ends at 0.
The string is valid if at the end lo == 0, meaning some valid interpretation closes every parenthesis perfectly.