Valid Parenthesis String

Given a string s made only of the characters '(', ')' and '*', return true if it can be a valid parenthesis string. Each '*' may stand for '(', for ')', or for an empty string. Valid means every '(' has a matching ')' to its right, and every ')' has a matching '(' to its left. The limit is 1 <= s.length <= 100. This is LeetCode 678.

The page gives two solutions. Solution 1 keeps a range of possible open counts and runs in O(1) space. Solution 2 pairs characters by index with two stacks.

Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "(*))"
Output: true
Explanation: the '*' becomes '(', giving "(())".
Example 3
Input: s = "(((*)"
Output: false
Explanation: three '(' need three closers, but only the '*' and one ')' can close them.

How to Think About It

Step 1: Without stars, one counter is enough

For plain parentheses, count unmatched openers: add 1 for '(' and subtract 1 for ')'. The string is valid when the count never drops below 0 and ends at 0. Valid Parentheses uses the same idea with a stack because it has several bracket types.

Step 2: Brute force over the stars

Each '*' has three choices, so trying them all costs O(3^k) for k stars. With 100 characters that is far too many. The choices only differ in how they move the counter, which suggests tracking the counter values instead of the choices.

Step 3: Track the set of possible counts

After reading a prefix, collect every open count that some choice of stars could produce. A '(' shifts every value up by 1, a ')' shifts every value down by 1, and a '*' turns each value v into v - 1, v and v + 1.

Starting from {0}, these moves never leave a hole. So the set is always a whole range of integers, and two numbers describe it: low, the smallest count, and high, the largest.

Step 4: Throw away negative counts

A count below 0 means a ')' closed something that was never opened, and no later character can repair that. So cut the range at 0 by setting low to at least 0. If even high is negative, every choice has failed, so return false at once.

Step 5: The answer

At the end, the string can be balanced exactly when 0 is still in the range. Since low never goes below 0, that is the test low == 0. This is a greedy scan: one pass, a small summary of every choice, and no backtracking.

Walkthrough

Solution 1 on Example 2, s = "(*))". The clamp to 0 does the work on the two closing characters.

Characterlow, high after the moveAfter clamping lowPossible open counts
(1, 11, 1{1}
*0, 20, 2{0, 1, 2}
)-1, 10, 1{0, 1}
)-1, 00, 0{0}

The scan ends with low = 0, so the answer is true. On Example 3, "(((*)", the range ends as 1 to 3: at least one opener stays unmatched, so the answer is false.

Solution 1: Greedy Range of Open Counts

The method reads the string once and keeps the smallest and largest number of unmatched '(' that any choice of stars could leave.

  • The three moves: '(' raises both ends, ')' lowers both ends, and '*' lowers low while raising high, since it can act as either bracket.
  • Early exit: high < 0 means there are more ')' than '(' and '*' together so far. The string ")(" fails on its first character.
  • The clamp: Math.max(low, 0) drops choices that went negative. The check on high comes first, so the clamp never pushes low above 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 == 0. Then low keeps counting a star as ')' even when nothing is open. "(*)" ends with low = -1 and returns false instead of true.

Java
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 '(', the other holds indices of unused '*'.

  • 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() and ignore the order. A star to the left of a '(' cannot close it, yet "*(" then returns true instead of false.

Java
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 Math.max for each.
  • Solution 1 space: O(1). Apart from the character array from toCharArray(), the whole state is the two integers low and high; using charAt instead would remove that copy too.
  • 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 Minimum Add to Make Parentheses Valid.