☕ DSA Java Articles

Topics › Greedy Algorithms › Easy Problems

Valid Paranthesis Checker

Hard TUF ID 545 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s made of the characters '(', ')' and '*'. Each '*' is a wildcard that may be read as '(', as ')', or as an empty string. Return true if some choice for the stars turns s into a valid parentheses string, meaning every '(' is closed by a later ')' and every ')' closes an earlier '('. The empty string is valid.

In Striver’s A2Z sheet this appears in the greedy section as “Valid Parenthesis Checker”; it is LeetCode 678, “Valid Parenthesis String”. Without stars it would be the ordinary balanced-brackets check.

Constraints: 1 ≤ |s| ≤ 100 on LeetCode. The greedy solution below is linear, so much longer strings are fine too.

Example 1

s = "(*))"
answer = true       // read '*' as '(' to get "(())"

Example 2

s = "(((*)"
answer = false      // three '(' need three closers, but only ')' and one '*' follow

The counter view

For a string of plain brackets, scan left to right with a counter open: add 1 for '(', subtract 1 for ')'. The string is valid exactly when open never drops below zero (no ')' arrives without a partner) and ends at zero (nothing is left unclosed). Order matters: ")(" has equal counts yet fails at the first character.

A star simply adds a choice: +1, -1 or 0. All three approaches search over those choices; they differ in how much of the search they keep.

Approach 1: Brute force, try every meaning of every star

Intuition. Follow the definition. Recurse over the string carrying the current open count. For a fixed bracket there is one way forward; for a star, try all three and succeed if any of them does. Any branch whose count goes negative is dead immediately.

Algorithm.

  1. tryAll(i, open): if open < 0, return false. If i == n, return open == 0.
  2. If s[i] is '(', recurse with open + 1; if ')', recurse with open - 1.
  3. If s[i] is '*', return tryAll(i + 1, open + 1) || tryAll(i + 1, open - 1) || tryAll(i + 1, open).
static boolean bruteForce(String s) {
    return tryAll(s, 0, 0);
}

static boolean tryAll(String s, int i, int open) {
    if (open < 0) return false;                     // a ')' arrived with nothing to close
    if (i == s.length()) return open == 0;
    char c = s.charAt(i);
    if (c == '(') return tryAll(s, i + 1, open + 1);
    if (c == ')') return tryAll(s, i + 1, open - 1);
    return tryAll(s, i + 1, open + 1)               // '*' as '('
            || tryAll(s, i + 1, open - 1)           // '*' as ')'
            || tryAll(s, i + 1, open);              // '*' as empty
}

Complexity. Time O(3^k) recursive calls for k stars, each path being up to n deep, so O(3^n) in the worst case. Space O(n) for the recursion. A string of 100 stars is hopeless.

Approach 2: Better, memoisation on (index, open)

Intuition. The future of a branch depends only on two numbers: where we are (i) and how many brackets are open (open). How we got there is irrelevant. Many different star choices lead to the same pair, so cache the answer for each pair. Since open can never exceed i, there are at most (n + 1)^2 states.

Algorithm.

  1. Allocate memo[n + 1][n + 1] of Boolean, where null means “not computed yet”.
  2. Run the same recursion as before, but return the cached value if present and store each computed answer.
static boolean better(String s) {
    int n = s.length();
    Boolean[][] memo = new Boolean[n + 1][n + 1];
    return solve(s, 0, 0, memo);
}

static boolean solve(String s, int i, int open, Boolean[][] memo) {
    if (open < 0) return false;
    if (i == s.length()) return open == 0;
    if (memo[i][open] != null) return memo[i][open];
    char c = s.charAt(i);
    boolean ans;
    if (c == '(') ans = solve(s, i + 1, open + 1, memo);
    else if (c == ')') ans = solve(s, i + 1, open - 1, memo);
    else ans = solve(s, i + 1, open + 1, memo) || solve(s, i + 1, open - 1, memo) || solve(s, i + 1, open, memo);
    memo[i][open] = ans;
    return ans;
}

Complexity. Time O(n^2): each of the O(n^2) states is computed once with constant work. Space O(n^2) for the table plus O(n) stack.

Approach 3: Optimal, greedy range of open counts

Intuition. Instead of following individual branches, track all possible values of open at once. Call the smallest possible value lo and the largest hi.

The key fact is that the set of possible values is always a contiguous range [lo, hi]. It starts as {0}; brackets shift a range, a star turns [lo, hi] into [lo - 1, hi + 1], which is still contiguous. So two integers describe the full state of Approach 2’s search at index i.

Two corrections keep the range honest. Negative counts are dead branches, so after each character we clamp lo up to 0. If even hi is negative, every branch is dead and the answer is false. At the end, the string is valid exactly when 0 is still possible, that is when lo == 0.

Algorithm.

  1. lo = hi = 0.
  2. For each character, update lo and hi as above.
  3. If hi < 0, return false. If lo < 0, set lo = 0.
  4. After the loop, return lo == 0.
static boolean optimal(String s) {
    int lo = 0, hi = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            lo++;
            hi++;
        } else if (c == ')') {
            lo--;
            hi--;
        } else {                    // '*': one fewer if it closes, one more if it opens
            lo--;
            hi++;
        }
        if (hi < 0) return false;   // too many ')' even if every '*' opened
        if (lo < 0) lo = 0;         // a negative count is not a real state; drop it
    }
    return lo == 0;
}

Dry run on s = "(*))":

i char lo hi note
0 ( 1 1  
1 * 0 2 open could be 0, 1 or 2
2 ) 0 1 lo was -1, clamped
3 ) 0 0 lo was -1, clamped

The loop ends with lo == 0, so the answer is true. On "(((*)" the range goes [1,1], [2,2], [3,3], [2,4], [1,3]; lo ends at 1, so at least one '(' always stays open and the answer is false.

Complexity. Time O(n): one pass. Space O(1): two integers.

Edge cases and pitfalls