The "Valid Parenthesis String" interview question is a medium-difficulty variant of the classic parentheses problem. In addition to ( and ), the string can contain asterisks *. An asterisk can be treated as a left parenthesis (, a right parenthesis ), or an empty string. This flexibility makes the validation much more complex than the standard version.
Companies like Meta, Amazon, and LinkedIn use the "Valid Parenthesis String" coding problem to see if a candidate can handle ambiguity and non-deterministic choices. It tests whether you can adapt the standard stack-based solution or if you can find a more optimized greedy approach to track the range of possible open bracket counts.
There are two main patterns: "Two Stacks" or "Greedy." The Greedy approach is more efficient, using two counters to track the minOpen and maxOpen brackets possible at any point. maxOpen increases with ( or *, while minOpen decreases with ) or *. If at any point maxOpen becomes negative, it's invalid. At the end, minOpen must be 0.
Consider the string: "(*)".
(: minOpen = 1, maxOpen = 1.*: minOpen could be 0 (if * is )), maxOpen could be 2 (if * is ().): minOpen stays 0 (can't go below 0), maxOpen becomes 1.minOpen is 0. Result: Valid. (The * acted as an empty string).A common mistake is using a single stack and trying to backtrack for every *, which leads to an exponential O(3ⁿ) complexity. Another mistake is forgetting that minOpen cannot drop below zero during the iteration, as you cannot have more closing brackets than potential opening ones at any intermediate step.
While the stack approach is intuitive, mastering the "Greedy interview pattern" for this problem is highly impressive. It shows that you can optimize a solution from O(n) space to O(1) space, which is a major plus in technical interviews for senior roles.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Minimum Additions to Make Valid String | Medium | Solve | |
| Minimum Add to Make Parentheses Valid | Medium | Solve | |
| Check if a Parentheses String Can Be Valid | Medium | Solve | |
| Minimum Deletions to Make String Balanced | Medium | Solve | |
| Maximum Score From Removing Substrings | Medium | Solve |