Valid Parenthesis String — Solution in Python, Java & C++
Valid Parenthesis String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Valid Parenthesis String is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Greedy, Stack
- Asked at: Amazon, Google, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s containing only '(', ')' and '*', return true if s is valid.
The rules are the usual bracket-matching rules, and a '*' may stand for '(', for ')', or for the empty string.
Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "(*)"
Output: true
Explanation: The star can be the empty string.
Example 3
Input: s = "(*))"
Output: true
Explanation: The star can be an opening bracket.
Constraints
1 <= s.length <= 40s consists of '(', ')' and '*'.
Hints for Valid Parenthesis String
Hint 1
Instead of trying every meaning of every star, track the range of possible open-bracket counts.
Hint 2
loassumes every star is a closing bracket (or empty);hiassumes every star is an opening bracket.Hint 3
If
hiever drops below zero there are too many closers to fix; clamploat zero, and at the end the string is valid iffloreached 0.
How to solve Valid Parenthesis String
Track the range of possible open-bracket counts: lo treats every star as a closer, hi treats every star as an opener. The string is valid if hi never goes negative and lo can end at 0.
Approach
- Set
lo = hi = 0. - For
(: increment both. For): decrement both. For*:lo -= 1,hi += 1. - If
hi < 0, returnfalse; clamploto 0. - Return
lo == 0.
Why it works
Every achievable open-count after a prefix lies in [lo, hi], and every integer in that range is achievable because stars can be re-assigned one at a time. hi < 0 means even all-openers cannot absorb the closers; clamping lo discards impossible negative counts. Ending with 0 in range means some assignment balances.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting to clamp
lolets a later("cancel" an impossible negative balance. - Trying every star assignment is exponential; two stacks (one for
(, one for*) is the other linear approach.
Reference solution
Python
def checkValidString(s: str) -> bool:
lo = hi = 0
for ch in s:
if ch == "(":
lo += 1
hi += 1
elif ch == ")":
lo -= 1
hi -= 1
else:
lo -= 1
hi += 1
if hi < 0:
return False
if lo < 0:
lo = 0
return lo == 0Java
public static boolean checkValidString(String s) {
int lo = 0, hi = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') { lo++; hi++; }
else if (c == ')') { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) return false;
if (lo < 0) lo = 0;
}
return lo == 0;
}C++
bool checkValidString(string s) {
int lo = 0, hi = 0;
for (char c : s) {
if (c == '(') { lo++; hi++; }
else if (c == ')') { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) return false;
if (lo < 0) lo = 0;
}
return lo == 0;
}JavaScript
var checkValidString = function(s) {
let lo = 0, hi = 0;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === "(") { lo++; hi++; }
else if (c === ")") { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) return false;
if (lo < 0) lo = 0;
}
return lo === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming