Valid Parenthesis String
Asked at Apple
Problem
Given a string s containing characters "(" , ")" , and "", determine if the string is valid. An empty string is valid. Each "(" must have a matching ")" in the correct order. "" can be treated as "(", ")", or an empty string.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
How to Think About It
Brute force: try all possible replacements of * (three choices each) and check validity.
DP approach: dp[i][j] = true if substring s[i..j] is valid. Base: single * is valid, empty is valid.
Greedy with two counters: track the range of possible open parentheses counts.
Low tracks minimum open count (treat * as ")"), high tracks maximum open count (treat * as "(").
At the end, low must be 0. If high ever goes negative, return false early.
Optimal Approach
Use two counters: low and high. low represents the minimum possible open parentheses, high the maximum. For "(", increment both. For ")", decrement both. For "*", decrement low and increment high (simulating all three choices). Clamp low to 0. If high goes below 0, return false. At the end, low == 0 means a valid string exists. O(n) time, O(1) space.
What Trips People Up in Real Interviews
Clarify: can * appear anywhere, including at the start or end.
The greedy two-pointer approach is the most elegant and runs in O(n) time.
DP is O(n^2) time and space — acceptable but less efficient.
Be careful: low should never go below 0 (clamp it).
If high is negative at any point, it means too many ")" have appeared — return false.
Solution Code
class Solution:
def checkValidString(self, s: str) -> bool:
low = high = 0
for ch in s:
if ch == '(':
low += 1
high += 1
elif ch == ')':
low = max(low - 1, 0)
high -= 1
else:
low = max(low - 1, 0)
high += 1
if high < 0:
return False
return low == 0Frequently Asked Questions
What is the Valid Parenthesis String problem?
Given a string s containing characters "(" , ")" , and "*", determine if the string is valid. An empty string is valid. Each "(" must have a matching ")" in the correct order. "*" can be treated as "(", ")", or an empty string.
How do you solve Valid Parenthesis String?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Valid Parenthesis String?
Valid Parenthesis String is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Valid Parenthesis String?
- Clarify: can * appear anywhere, including at the start or end.
- The greedy two-pointer approach is the most elegant and runs in O(n) time.
- DP is O(n^2) time and space — acceptable but less efficient.
- Be careful: low should never go below 0 (clamp it).
- If high is negative at any point, it means too many ")" have appeared — return false.