Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
'(' must have a corresponding right parenthesis ')'.')' must have a corresponding 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 "".
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "(*)" Output: true
Example 3:
Input: s = "(*))" Output: true
Constraints:
1 <= s.length <= 100s[i] is '(', ')' or '*'.Problem Overview: You receive a string containing three characters: (, ), and *. The asterisk acts as a wildcard and can represent (, ), or an empty string. The task is to determine whether the string can be interpreted as a valid parentheses sequence.
This problem looks like a typical parentheses validation task but becomes tricky because * can play multiple roles. You need a strategy that keeps track of possible interpretations without trying every combination. Efficient solutions rely on techniques from stack processing and greedy algorithms, both commonly used when validating structured strings.
Approach 1: Stack-based Tracking (O(n) time, O(n) space)
This approach uses two stacks: one for indices of ( characters and another for indices of *. While iterating through the string, push positions of opening brackets and asterisks onto their respective stacks. When encountering ), try to match it with the most recent (. If none exists, use a * as a substitute opening bracket. After processing the entire string, there may still be unmatched (. Pair them with later * characters by comparing indices to ensure ordering is valid. This approach works because stacks naturally model the nested structure of parentheses while allowing deferred decisions for wildcard characters.
Approach 2: Greedy Balance Range (O(n) time, O(1) space)
The greedy solution tracks the range of possible open-parenthesis counts instead of exact matches. Maintain two counters: low (minimum possible open brackets) and high (maximum possible open brackets). When reading (, increment both. When reading ), decrement both. When reading *, treat it flexibly: decrement low (as if it were )) and increment high (as if it were (). Clamp low to zero because open counts cannot be negative. If high ever drops below zero, the string cannot be valid. By the end of the scan, a valid configuration exists if low == 0. This method works because it keeps track of the entire feasible range of interpretations without explicitly constructing them.
Recommended for interviews: The greedy balance method is the solution most interviewers expect. It runs in O(n) time with O(1) space and demonstrates strong reasoning about state ranges rather than brute-force enumeration. The stack-based approach is still valuable during interviews because it shows clear thinking about matching order and wildcard handling, but the greedy method highlights deeper optimization skills.
In this approach, we use two stacks. One stack will store indices of '(' characters, and the other will store indices of '*' characters as we traverse the string.
If we find a ')' character and there are unmatched '(' in the stack, we pop one out as it can be matched. If no '(' is available, we match using '*'. After processing, all unmatched '(' should be balanced by '*' appearing after them in the string.
The function uses two stacks to keep track of the positions of '(' and '*' characters. When encountering ')', it attempts to match it using an available '(' or '*'. After scanning the string, any remaining unmatched '(' is checked against '*' to ensure validity.
Python
JavaScript
Time Complexity: O(n), as we process each character of the string once.
Space Complexity: O(n), due to use of two stacks to track indices of '(' and '*'.
This approach involves maintaining two balance counts: one for keeping a minimal balance and the other for maximal considering '*' as both '(' and ')'.
As we traverse, the minimal balance ensures ')' never exceeds '(' without the aid of '*', while the maximal balance accounts for replacing '*' with '('. If at any point the maximal balance is negative, then parentheses can't be balanced.
The C++ solution uses two balance counters. It iterates over the string adjusting minBal and maxBal based on the character encountered ('(', ')', or '*'). The maxBal ensures we never have more ')' than possible '('. Negative minBal is reset to reflect reality where '*' can become '(' or empty.
Time Complexity: O(n), as we traverse the string once.
Space Complexity: O(1), since we use a constant amount of extra space regardless of the input size.
Let dp[i][j] be true if and only if the interval s[i], s[i+1], ..., s[j] can be made valid. Then dp[i][j] is true only if:
s[i] is '*', and the interval s[i+1], s[i+2], ..., s[j] can be made valid;or, s[i] can be made to be '(', and there is some k in [i+1, j] such that s[k] can be made to be ')', plus the two intervals cut by s[k] (s[i+1: k] and s[k+1: j+1]) can be made valid;
Time Complexity: O(n^3), where n is the length of the string. There are O(n^2) states corresponding to entries of dp, and we do an average of O(n) work on each state.
O(n^2).Scan twice, first from left to right to make sure that each of the closing brackets is matched successfully, and second from right to left to make sure that each of the opening brackets is matched successfully.
O(n), where n is the length of the string.O(1).| Approach | Complexity |
|---|---|
| Stack-based Approach | Time Complexity: O(n), as we process each character of the string once. |
| Greedy Approach with Balances | Time Complexity: O(n), as we traverse the string once. |
| Dynamic Programming | — |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Tracking | O(n) | O(n) | When you want a clear simulation of matching parentheses and explicit index tracking. |
| Greedy Balance Range | O(n) | O(1) | Preferred for interviews and production due to constant space and elegant range tracking. |
L11. Valid Parenthesis String | Multiple Approaches • take U forward • 189,606 views views
Watch 9 more video solutions →Practice Valid Parenthesis String with our built-in code editor and test cases.
Practice on FleetCode