Valid Parenthesis String
Given a string s'('')''*''*''('')''('')'')''('1 <= s.length <= 100
The page gives two solutions.
Example 1
Output: true
Example 2
Output: true
Explanation: the
'*''('Example 3
Output: false
Explanation: three
'(''*'')'How to Think About It
Step 1: Without stars, one counter is enough
For plain parentheses, count unmatched openers: add 1 for '('')'
Step 2: Brute force over the stars
Each '*'
Step 3: Track the set of possible counts
After reading a prefix, collect every open count that some choice of stars could produce. A '('')''*'
Starting from {0}, these moves never leave a hole. So the set is always a whole range of integers, and two numbers describe it: lowhigh
Step 4: Throw away negative counts
A count below 0 means a ')'lowhigh
Step 5: The answer
At the end, the string can be balanced exactly when 0 is still in the range. Since lowlow == 0
Walkthrough
Solution 1 on Example 2, s = "(*))"
| Character | low, high after the move | After clamping low | Possible open counts |
|---|---|---|---|
| ( | 1, 1 | 1, 1 | {1} |
| * | 0, 2 | 0, 2 | {0, 1, 2} |
| ) | -1, 1 | 0, 1 | {0, 1} |
| ) | -1, 0 | 0, 0 | {0} |
The scan ends with low = 0"(((*)"
Solution 1: Greedy Range of Open Counts
The method reads the string once and keeps the smallest and largest number of unmatched '('
- The three moves:
raises both ends,'(' lowers both ends, and')' lowers'*' while raisinglow , since it can act as either bracket.high - Early exit:
means there are morehigh < 0 than')' and'(' together so far. The string'*' fails on its first character.")(" - The clamp:
drops choices that went negative. The check onMath.max(low, 0) comes first, so the clamp never pusheshigh abovelow .high - Edge cases:
returns true because the star can be empty."*" returns false because nothing to the right can close the"*(" .'('
A common mistake is to leave out the clamp and return low == 0low')'"(*)"low = -1
public class ValidParenthesisString {
public boolean checkValidString(String s) {
int low = 0; // fewest unmatched '(' possible so far
int high = 0; // most unmatched '(' possible so far
for (char c : s.toCharArray()) {
if (c == '(') {
low++;
high++;
} else if (c == ')') {
low--;
high--;
} else { // '*' can close one, open one, or do nothing
low--;
high++;
}
if (high < 0) {
return false; // too many ')' even if every '*' is '('
}
low = Math.max(low, 0); // a negative count is never a valid choice
}
return low == 0;
}
}
Solution 2: Two Stacks of Indices
This version decides concretely which character pairs with which. One stack holds indices of unmatched '(''*'
- Closing a
: pop a real')' if there is one, otherwise pop a star to act as'(' . Saving stars keeps them free for later work, and either partner sits to the left of the'(' .')' - Leftover openers: after the scan, each remaining
needs a star to its right acting as'(' . Both stacks have their largest index on top, so the latest')' is matched to the latest star.'(' - Leftover stars: stars that are never used simply become empty strings, so extra stars do no harm.
- Edge cases:
returns true with the star as"(*" , and')' returns true with the star as"((*)" for the inner opener.')'
A common mistake is to finish with opens.size() <= stars.size()'('"*("
import java.util.ArrayDeque;
import java.util.Deque;
public class ValidParenthesisStringTwoStacks {
public boolean checkValidString(String s) {
Deque<Integer> opens = new ArrayDeque<>(); // indices of unmatched '('
Deque<Integer> stars = new ArrayDeque<>(); // indices of unused '*'
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
opens.push(i);
} else if (c == '*') {
stars.push(i);
} else if (!opens.isEmpty()) {
opens.pop(); // a real '(' is the best partner
} else if (!stars.isEmpty()) {
stars.pop(); // otherwise a '*' acts as '('
} else {
return false;
}
}
while (!opens.isEmpty()) {
if (stars.isEmpty() || stars.peek() < opens.peek()) {
return false; // no '*' to the right of this '('
}
opens.pop();
stars.pop(); // that '*' acts as ')'
}
return true;
}
}
Complexity
- Solution 1 time: O(n). The loop reads each of the n characters once and does a fixed number of additions, one comparison and one
for each.Math.max - Solution 1 space: O(1). Apart from the character array from
, the whole state is the two integerstoCharArray() andlow ; usinghigh instead would remove that copy too.charAt - Solution 2 time: O(n). Every index is pushed at most once and popped at most once, either during the scan or in the final matching loop, and each push or pop is constant time.
- Solution 2 space: O(n) for the two stacks. In a string such as
every index is still waiting on a stack when the scan ends."((((**"
Which One to Use
Both solutions agree on every string up to length 10 and on 200,000 random strings checked against a brute force. Solution 1 is shorter and uses constant memory, so it is the usual interview answer. Its correctness rests on the claim that the possible counts form a range, which you should be ready to explain. Solution 2 is easier to trust at first sight because it builds an actual pairing. It also adapts if you later need to report which star plays which role.
For a related task that counts the fewest brackets to add, see