2116. Check if a Parentheses String Can Be Valid - Detailed Explanation
Problem Statement
You are given a string s containing only the characters '(', ')', and '*'. The character '*' can represent:
- a left parenthesis
'(', - a right parenthesis
')', or - an empty string (i.e. it can be removed).
Return true if s can be made valid after replacing every '*' with one of the above possibilities. A string is valid if:
- Every left parenthesis
'('has a corresponding right parenthesis')'. - Every right parenthesis
')'has a corresponding left parenthesis'('. - Left parentheses must appear before the corresponding right parentheses.
- An empty string is valid.
Examples
Example 1
Input:
s = "()*"
Output:
true
Explanation:
- The
'*'can be treated as an empty string, making the string"()"which is valid. - Alternatively,
'*'could represent either'('or')'but at least one replacement makes it valid.
Example 2
Input:
s = "(*)"
Output:
true
Explanation:
- Here,
'*'can be an empty string, resulting in"()"which is valid.
Example 3
Input:
s = "(*))"
Output:
true
Explanation:
- The
'*'can be interpreted as'(', which yields"(()))", and then the extra right parenthesis can be balanced by the chosen replacement. Alternatively, by different replacement choices, one can balance the string.
Hints
-
Greedy Approach:
- Think in terms of tracking the range of possible open parenthesis counts as you scan the string.
- Use two counters: one for the lowest possible number of open parentheses and one for the highest.
- Update these counters when you see
'(',')', or'*'(which can act as(,), or empty).
-
Dynamic Programming:
- Consider DP where
dp[i][j]means whether the firsticharacters can achieve exactlyjopen parentheses. - This approach is more straightforward but less efficient.
- Consider DP where
-
Stack Approach:
- Use stacks to keep track of indices for
'('and'*'. Then try to match any unmatched'('with available'*'. - Finally, ensure that any remaining
'('can be balanced by an appropriate'*'coming later.
- Use stacks to keep track of indices for
Approach 1: Greedy (Optimal) Solution
Idea
- Traverse the string while maintaining two variables:
lo: the lowest possible number of open left parentheses.hi: the highest possible number of open left parentheses.
- For each character:
- If it’s
'(': increment bothloandhi. - If it’s
')': decrement bothloandhi. - If it’s
'*': decrementlo(treat as')') and incrementhi(treat as'(').
- If it’s
- Clamp
loto a minimum of 0 (you cannot have a negative number of open parentheses). - If at any point
hibecomes negative, it means there are too many')'and no replacement can fix that. - At the end, if
lois 0, the string can be valid.
Step-by-Step Walkthrough with Table
Consider s = "(*))":
| Step | Character | Action | lo update | hi update | Comment |
|---|---|---|---|---|---|
| 1 | ( | It’s '(' → add one open parenthesis | lo = 0 + 1 = 1 | hi = 0 + 1 = 1 | One open parenthesis |
| 2 | * | It’s '*' → can be ')' (decrease) or '(' (increase) | lo = 1 - 1 = 0 | hi = 1 + 1 = 2 | Range becomes [0, 2] |
| 3 | ) | It’s ')' → decrease open count | lo = 0 - 1 = -1 → clamp to 0 | hi = 2 - 1 = 1 | lo clamped: [0, 1] |
| 4 | ) | It’s ')' → decrease open count | lo = 0 - 1 = -1 → clamp to 0 | hi = 1 - 1 = 0 | Final range: [0, 0] (valid since lo==0) |
Since lo is 0 at the end, the string can be valid.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string.
- Space Complexity: O(1) (constant extra space for counters).
Python Code
Java Code
Approach 2: Dynamic Programming (Alternative)
Idea
Define dp[i][j] to be true if the first i characters can have exactly j open parentheses.
- Start with
dp[0][0] = true. - For each character:
- If it’s
'(': then for eachj,dp[i+1][j+1] |= dp[i][j]. - If it’s
')': then for eachj > 0,dp[i+1][j-1] |= dp[i][j]. - If it’s
'*': it can be treated as'(',')', or empty.
- If it’s
- At the end, if any
dp[n][0]istrue, the string can be valid.
Complexity
- Time Complexity: O(n²) where n is the length of the string.
- Space Complexity: O(n²).
Python Code
Java Code
Common Mistakes & Edge Cases
-
Negative Open Count:
Ensure that the lower bound of open parentheses never becomes negative. In the greedy approach, we usemax(lo, 0)after each update. -
Early Termination:
If at any point the maximum possible count (hi) becomes negative, the string cannot be valid. -
All
'*'String:
A string of all'*'is always valid because each'*'can be treated as an empty string. -
Empty String:
An empty string should returntrue. -
Balance Between Choices:
In the DP approach, ensure you consider all three possibilities for'*'(empty,(,)).
Related Problems
-
Valid Parentheses:
Given a string containing just the characters'(',')','{','}','[', and']', determine if the input string is valid. (This problem is simpler since no wildcard characters are involved.) -
Longest Valid Parentheses:
Find the length of the longest valid (well-formed) parentheses substring. -
Remove Invalid Parentheses:
Remove the minimum number of invalid parentheses to make the input string valid and return all possible results. -
Generate Parentheses:
Generate all combinations of well-formed parentheses for a given number of pairs.
Summary
We have covered two main approaches to solve the Check if a Parentheses String Can Be Valid problem:
-
Greedy Approach:
- Maintain a range of possible open parentheses counts using two counters (
loandhi). - Time Complexity: O(n), Space Complexity: O(1).
- Maintain a range of possible open parentheses counts using two counters (
-
Dynamic Programming Approach:
- Use a DP table where
dp[i][j]indicates if the firsticharacters can have exactlyjopen parentheses. - Time Complexity: O(n²), Space Complexity: O(n²).
- Use a DP table where
Both approaches have their merits. The greedy solution is optimal in terms of time and space, while the DP solution is more intuitive for those who think in terms of state transitions.
GET YOUR FREE
Coding Questions Catalog
