Valid Parenthesis String With `*` Wildcard: Greedy Min/Max Open-Count Range

• Wildcard parenthesis validation – checks whether a string of round brackets and * wildcards can be made valid, where each * may act as (, ), or empty.
• Greedy range tracking – instead of exploring all interpretations, the algorithm tracks a low and high of possible open-bracket counts in a single pass.
• Low clamp rule – after every character, low is clamped to zero because the open count can never be negative in reality.
• High rejection rule – if high ever drops below zero, even the most optimistic interpretation has too many closers, so the string is invalid.
• End acceptance rule – the string is valid if and only if low equals zero at the end, meaning zero unmatched openers is achievable.

What is the Valid Parenthesis String with Wildcard problem?

The problem gives you a string containing three types of characters: opening brackets (, closing brackets ), and asterisk wildcards *. Each asterisk can be interpreted as an opening bracket, a closing bracket, or an empty string. You must determine whether there exists at least one interpretation of all the wildcards that makes the entire string a valid parenthesis sequence.

A valid parenthesis sequence is one where every opening bracket has a matching closing bracket, every closing bracket has a matching opening bracket, and at no point while reading left to right does the count of closers exceed the count of openers.

package com.bank.core;

// Input: "(*)"
// The * can be ')' making "())", or '(' making "(()", or empty making "()"
// At least one interpretation "()" is valid, so the answer is true

Why does a naive approach fail?

Without wildcards, a single integer counter suffices: increment on (, decrement on ), reject if it goes negative, accept if it ends at zero. But each * has three interpretations, so a string with k asterisks has 3^k possible readings. Trying all of them is exponential and far too slow for strings of length 10,000 or more.

The insight is that we do not need to track every specific interpretation. We only need to know the range of values the open-bracket count could currently take under any valid interpretation. If zero is achievable at the end, some interpretation works.

package com.bank.core;

// Brute force: 3^k interpretations for k wildcards
// For k = 20, that is over 3 billion checks
// Greedy range: one pass, constant space

How does the greedy low-high range work?

You maintain two variables: low (the minimum possible open count) and high (the maximum possible open count), both starting at zero. As you scan each character:

• ( : both low and high increase by one, because an opener always adds an open bracket.
• ) : both low and high decrease by one, because a closer always removes one.
• ***** : low decreases by one (the asterisk could be )) and high increases by one (the asterisk could be (). The empty interpretation falls within this expanded range.

After processing each character, apply two guards:

1. If high < 0, return false: even the most optimistic interpretation has more closers than openers.
2. If low < 0, clamp low to zero: you can never have fewer than zero open brackets.

package com.bank.service;

public class WildcardParenthesisValidator {

    public boolean isValid(String s) {
        int low = 0;
        int high = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                low--;
                high--;
            } else { // '*'
                low--;   // treat as ')'
                high++;  // treat as '('
            }

            if (high < 0) return false; // too many closers
            if (low < 0) low = 0;       // clamp to zero
        }

        return low == 0;
    }
}

javac com/bank/service/WildcardParenthesisValidator.java

Why must we clamp low to zero?

The low variable represents the fewest open brackets possible under any interpretation so far. But the open-bracket count can never actually be negative: you cannot have negative one unmatched openers. When low drops below zero, it means some interpretations would need a closer to match a nonexistent opener, but those interpretations simply treat the asterisk as empty instead, so the real minimum is zero.

Without the clamp, low drifts to large negative values, and at the end checking low == 0 would fail for strings that are actually valid. This is the single most common bug in this problem.

package com.bank.core;

// Example: "*)"
// After '*': low = -1, high = 1 -> clamp low to 0
// After ')': low = -1, high = 0 -> clamp low to 0
// End: low == 0, so valid (the * acts as '(')

// Without clamping:
// After '*': low = -1, high = 1
// After ')': low = -2, high = 0
// End: low == -2, incorrectly reports invalid

Why does high going negative mean immediate failure?

The high variable is the maximum possible open count: the best-case scenario where every ambiguous choice favors openers. If even this optimistic count goes negative, it means every possible interpretation has seen more closing brackets than opening brackets at this point, and no future characters can fix that because a parenthesis sequence must never have a negative running balance. So we short-circuit and return false.

package com.bank.core;

// Example: ")("
// After ')': low = -1, high = -1 -> high < 0, return false
// No wildcard can fix a closer appearing before any opener

Why is the acceptance test low equals zero, not low at most zero?

After clamping, low is always non-negative, so low <= 0 would just mean low == 0. But the deeper reason is that low represents the minimum achievable open count at the end. The string is valid only if we can end with exactly zero open brackets. Since the range from low to high is continuous and every integer in between is achievable by choosing appropriate wildcard interpretations, zero is achievable precisely when low is zero (or equivalently, when low <= 0 after clamping, which is the same as low == 0).

If low > 0 at the end, even the most aggressive use of wildcards as closers still leaves unmatched openers.

package com.bank.core;

// Example: "((*"
// After '(': low=1, high=1
// After '(': low=2, high=2
// After '*': low=1, high=3
// End: low=1 != 0, so invalid
// Even treating * as ')' leaves one unmatched '('

How does this compare to the two-stack approach?

An alternative solution uses two stacks: one storing indices of ( characters and another storing indices of * characters. When a ) appears, it matches against the opener stack first, then the wildcard stack. At the end, remaining openers try to match remaining wildcards that appear after them. This approach is correct and runs in O(n) time, but it uses O(n) space and requires more careful index bookkeeping.

| Aspect | Greedy low-high range | Two-stack approach |
|---|---|---|
| Time complexity | O(n) | O(n) |
| Space complexity | O(1) | O(n) |
| Code complexity | Simple single loop | Two stacks with index tracking |
| Handles all edge cases | Yes, with clamp | Yes, with index comparison |

package com.bank.service;

import java.util.ArrayDeque;
import java.util.Deque;

public class TwoStackValidator {

    public boolean isValid(String s) {
        Deque<Integer> openers = new ArrayDeque<>();
        Deque<Integer> stars = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                openers.push(i);
            } else if (c == '*') {
                stars.push(i);
            } else {
                if (!openers.isEmpty()) openers.pop();
                else if (!stars.isEmpty()) stars.pop();
                else return false;
            }
        }

        while (!openers.isEmpty() && !stars.isEmpty()) {
            if (openers.pop() > stars.pop()) return false;
        }
        return openers.isEmpty();
    }
}

What are common mistakes?

The most frequent mistake is forgetting to clamp low to zero. Without clamping, low drifts to large negative values and the final check low == 0 fails for valid strings.

Another mistake is treating the problem as a simple counter problem by ignoring the range. A single counter cannot represent the ambiguity of wildcards.

package com.bank.core;

// WRONG: single counter approach
public class WrongValidator {
    public boolean isValid(String s) {
        int open = 0;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '*') open++;
            else open--;
            if (open < 0) return false;
        }
        return open == 0; // Fails on "*" (should be true, reports false)
    }
}

// CORRECT: greedy range
public class CorrectValidator {
    public boolean isValid(String s) {
        int low = 0, high = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') { low++; high++; }
            else if (c == ')') { low--; high--; }
            else { low--; high++; }
            if (high < 0) return false;
            if (low < 0) low = 0;
        }
        return low == 0;
    }
}

What are the edge cases?

Several edge cases deserve attention: an empty string is trivially valid, a string of only asterisks is valid because each can be empty, a string with no wildcards reduces to the standard parenthesis check, and a single * is valid because it can be empty.

package com.bank.core;

// Edge case 1: empty string
// low=0, high=0, return true

// Edge case 2: "***"
// After each *: range widens but low clamped to 0
// End: low=0, return true (all treated as empty)

// Edge case 3: "((("
// No wildcards to help, low=3 at end, return false

// Edge case 4: single "*"
// low=0, high=1 after clamp, return true

What about a banking use case?

At the National Bank of India, transaction grouping templates use brackets to define nested payment batches and wildcards for optional sub-groups. Rajesh must validate that a template can be interpreted as a properly nested structure before the batch processor accepts it.

package com.bank.service;

import java.math.BigDecimal;

public class BatchTemplateValidator {

    private final WildcardParenthesisValidator validator =
        new WildcardParenthesisValidator();

    public boolean validateBatchTemplate(String template) {
        if (template == null || template.isEmpty()) {
            return true; // empty template is trivially valid
        }
        return validator.isValid(template);
    }

    public static void main(String[] args) {
        BatchTemplateValidator btv = new BatchTemplateValidator();

        String template1 = "(*)";
        String template2 = "(*))";
        String template3 = "((*)";

        System.out.println(template1 + " -> " + btv.validateBatchTemplate(template1));
        System.out.println(template2 + " -> " + btv.validateBatchTemplate(template2));
        System.out.println(template3 + " -> " + btv.validateBatchTemplate(template3));
    }
}

(*) -> true
(*)) -> true
((*) -> true

What should a senior engineer know?

A senior engineer should recognize that the greedy range approach is a special case of interval arithmetic applied to a counting problem. The low-high pair is effectively a reachability interval, and each character is an interval transformation. This generalizes: any problem where a counter is updated by operations with bounded ambiguity can use the same technique.

For production systems, the constant-space single-pass nature makes this suitable for streaming validation of very long templates without buffering the entire input. The algorithm can also be extended to multiple bracket types by tracking a range per bracket type, though the interactions between types require more careful analysis.

package com.bank.core;

// Time:  O(n) single pass
// Space: O(1) two integers
// The low-high range is an interval arithmetic technique
// Generalizes to any bounded-ambiguity counter problem