Valid Parenthesis String
Given a string `s` containing only three types of characters: `'('`, `')'` and `'*'`, return `true` if `s` is valid. The following rules define a valid string: - Any left parenthesis `'('` must have a corresponding right parenthesis `')'`. - Any right parenthesis `')'` must have a corresponding left parenthesis `'('`. - Left parenthesis `'('` must go before the corresponding right parenthesis `')'`. - `'*'` could be treated as a single right parenthesis `')'` or a single left parenthesis `'('` or an empty string `""`.
Examples
Constraints
1 <= s.length <= 100s[i] is '(', ')' or '*'
Greedy with Range
Approach
Instead of keeping track of exactly how many open parentheses we have (which varies because of `*`), we keep track of the *range* of possible open parentheses. Let `leftMin` be the minimum number of open parentheses we must have, and `leftMax` be the maximum number of open parentheses we could have. For each character: - If `(`, both `leftMin` and `leftMax` increment. - If `)`, both `leftMin` and `leftMax` decrement. - If `*`, `leftMin` decrements (treat as `)`) and `leftMax` increments (treat as `(`). At any point, if `leftMax < 0`, it means we have too many `)` and even treating all `*` as `(` isn't enough, so return false. If `leftMin < 0`, we just reset it to 0 because we cannot have a negative number of required open parentheses (we just treat the `*` as empty instead of `)`). At the end, if `leftMin == 0`, we can form a valid string.
Complexity Analysis
Time complexity is O(n) for a single pass through the string. Space complexity is O(1) for keeping track of the range.
class Solution { public boolean checkValidString(String s) { int leftMin = 0; int leftMax = 0; for (char c : s.toCharArray()) { if (c == '(') { leftMin++; leftMax++; } else if (c == ')') { leftMin--; leftMax--; } else { // '*' leftMin--; leftMax++; } // If the maximum possible open parens is negative, it's invalid if (leftMax < 0) { return false; } // We can't have negative required open parens if (leftMin < 0) { leftMin = 0; } } return leftMin == 0; }}