DSA problem
Valid Parenthesis String
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid. The string is valid if all parentheses match, every '(' must have a matching ')' and vice versa, every ')' must be preceded by a corresponding '(', and each '*' could be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string "".
The wildcard '*' makes this much harder than ordinary parenthesis validation — at each position, '*' has three possible interpretations, so a naive brute force would be exponential. Backtracking with memoization on (index, balance) brings it down to O(n^2), but we can do better.
The stack approach uses two stacks: one of indices of '(' and one of indices of '*'. When we see ')', prefer to match against an unmatched '(' (the top of the left-paren stack), otherwise consume a '*' as a right parenthesis. After the scan, leftover '(' must each be paired with a '*' that appears LATER in the string (so the '*' plays the role of ')'). We can verify that by comparing the top indices: every remaining '(' must have a star with a strictly larger index.
An even sleeker O(1)-space alternative is the greedy lo/hi technique: track the minimum and maximum possible count of unmatched '(' seen so far. On '(', both increase; on ')', both decrease; on '*', lo decreases (star acts as ')' or empty) and hi increases (star acts as '('). Clamp lo at 0 because the balance can never legitimately be negative. The string is valid iff hi never goes negative and lo ends at 0. This runs in O(n) time, O(1) space — but the canonical stack solution is below.
Examples
s = "()"trues = "(*)"trues = "(*))"trueConstraints
- 1 <= s.length <= 100
- s[i] is '(', ')' or '*'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.