Wildcard Parenthesis Validator

You're sitting in an Amazon interview room. The interviewer writes three characters on the whiteboard.

(, ), and *

"Here's an interesting twist on the classic parentheses validation problem," they say, tapping the asterisk. "This wildcard can be a left parenthesis, a right parenthesis, or nothing at all. Can you determine if a string containing these characters can possibly be valid?"

I've watched this problem stump brilliant engineers. Others solve it with remarkable elegance. The difference? Understanding that sometimes the best approach isn't the obvious one. Tech giants love this problem precisely because it separates candidates who default to brute force from those who pause, think, and find the insight hiding in plain sight.

TL;DR

Track the range of possible unmatched opening parentheses using two counters: low (minimum) and high (maximum). For (, increment both. For ), decrement both. For *, decrement low and increment high. If high goes negative, return false immediately. If low goes negative, reset it to zero. The string is valid if low equals zero at the end. This greedy approach runs in O(n) time and O(1) space, avoiding the exponential cost of testing all wildcard interpretations.

Why This Problem Matters

The wildcard parenthesis validator tests more than string manipulation skills. It reveals whether you can find elegant solutions when faced with ambiguity.

Think about the scale here. Google processes billions of search queries with nested operators. Excel validates complex formulas across millions of spreadsheets. AWS configuration files nest deeply with optional parameters. These systems all face the same fundamental challenge. How do you validate complex patterns when some elements are uncertain?

Master this problem, and you'll develop an intuition that extends far beyond parentheses. The same thinking applies to compiler design, regular expression engines, and even natural language processing where ambiguity is the norm, not the exception.

Understanding the Problem

Let's break down what we're dealing with.

We have a string containing only three types of characters: (, ), and *. Our task is determining whether the string can be valid, where each wildcard * can act as an opening parenthesis, a closing parenthesis, or simply disappear.

The catch? We don't need all interpretations to work. Just one.

Look at these examples to see the pattern emerge:

• "()" returns true (already valid)
• "(*)" returns true (the * can be empty)
• "(*))" returns true (the * becomes ()
• ")*((" returns false (no valid interpretation exists)

A brute force approach would test all possible interpretations. With n wildcards, that means checking 3^n combinations. Exponential complexity will timeout on any decent-sized input.

The efficient solution avoids this entirely. We can solve this in linear time. One pass. No recursion. No backtracking.

The Greedy Insight

The breakthrough comes from a shift in perspective. Instead of tracking exact counts, we track the range of possible open parentheses.

The approach is elegant once you understand the core insight.

Think of it this way. You see a ( and you know for certain you have one more open parenthesis. You see a ) and you definitely have one less. The wildcard creates three possibilities: it could increase our count (acting as (), decrease it (acting as )), or leave it unchanged (vanishing into thin air).

We handle this uncertainty by maintaining a range throughout our traversal: a minimum and maximum of possible open parentheses. As long as zero falls within this range at the end, we've found our valid interpretation.

Visualization of the Algorithm

Let's watch the range evolve as we process "(*))"

We're tracking two boundaries here. The low counter represents the minimum possible unmatched opening parentheses. The high counter tracks the maximum.

Notice how the wildcard creates divergence. When we hit that *, our range spreads. The minimum decreases (maybe it's a closing parenthesis), while the maximum increases (perhaps it's opening). This spreading captures all possibilities in a single pass.

The verdict comes at the end. If low equals zero, we've found at least one valid interpretation where everything balances perfectly.

Building the Solution

Let's walk through the algorithm construction.

First, we initialize both counters at zero. Makes sense, right? We haven't seen any parentheses yet.

As we traverse the string, each character updates our range. An opening parenthesis ( increases both boundaries since we definitely have one more unmatched opener. A closing parenthesis ) decreases both, as it must close something.

The wildcard is where things get clever. We decrease low (treating it as a potential closer) while increasing high (treating it as a potential opener). This single operation captures all three possibilities.

But wait, there are two edge cases to handle. If high ever goes negative, we've seen more closing parentheses than we could possibly match, even if every remaining character were an opener. Game over. Return false.

When low goes negative, that's different. We reset it to zero because we can't have negative open parentheses. But future wildcards might still balance things out.

The final check? Simple. If low equals zero, we've proven that at least one valid interpretation exists.

Implementation

Here's our elegant greedy solution:

Prefer a different language? Jump to solutions in Python, JavaScript, C++, Go, and Scala.

public class Solution {
  public boolean checkValidString(String s) {
    // Track the range of possible open parentheses
    int low = 0;   // Minimum possible unmatched '('
    int high = 0;  // Maximum possible unmatched '('

    for (int i = 0; i < s.length(); i++) {
      char ch = s.charAt(i);

      if (ch == '(') {
        // Definitely an open parenthesis
        low++;
        high++;
      } else if (ch == ')') {
        // Definitely closes a parenthesis
        low--;
        high--;
      } else {  // ch == '*'
        // Could be '(', ')', or empty
        low--;   // Treat as ')' for minimum
        high++;  // Treat as '(' for maximum
      }

      // Too many ')' - impossible to balance
      if (high < 0) {
        return false;
      }

      // Can't have negative open parentheses
      if (low < 0) {
        low = 0;
      }
    }

    // Valid if we can have exactly 0 unmatched parentheses
    return low == 0;
  }
}

Here's a more complex example: "((*)())"

Follow along with the counter evolution. We start with two opening parentheses, so both counters reach 2. Then comes the wildcard. Watch how it creates our first divergence, with low dropping to 1 while high jumps to 3.

The closing parenthesis brings both counters down. Then another opener pushes them back up. Another closer brings them down again.

The final closing parenthesis is interesting. It pushes low negative, triggering our reset to zero. Meanwhile, high lands at 1.

The result? low equals zero. Valid! The algorithm determined that treating the wildcard as empty creates a perfect balance.

Complexity Analysis

Time Complexity: O(n) - One pass through the string, visiting each character once. No nested loops, recursion, or backtracking.

Space Complexity: O(1) - Just two integer variables. No stack, no auxiliary data structures. When candidates realize their recursive O(n) solution can be replaced with two variables, the elegance becomes clear.

Common Pitfalls

After watching candidates tackle this problem, I see the same mistakes repeatedly.

The exact count trap: Trying to use a single counter fails because wildcards create three possibilities. You can't capture uncertainty with one number.

Forgetting to reset negative low: When low goes negative, don't give up! Reset to zero because future wildcards might balance things out.

Wrong final check: Checking high >= 0 would accept strings with unmatched opening parentheses. We need low == 0 for exact balance.

Missing early exit: When high < 0, you have too many closing parentheses to ever recover. Return false immediately.

Interview Tips

Here's my playbook for acing this problem when it comes up in your interview.

Start with small examples. Work through "(*)" on the whiteboard. Show each step, each counter update. Then scale up to "(*))". This builds intuition and shows the interviewer your thought process. Don't jump straight to coding.

Articulate the key insight early. Say something like, "Instead of tracking one exact count, I'll track a range of possibilities." This immediately signals that you understand why the naive approach fails.

Acknowledge alternatives before dismissing them. Mention the brute force approach and its 3^n complexity. Consider a two-pass solution. Maybe even discuss using a stack. Then explain why the range-tracking approach is superior. This demonstrates breadth of thinking.

Address edge cases proactively. What about an empty string? A string of all wildcards? No wildcards at all? Bring these up yourself. I've seen technically strong candidates stumble because they waited for the interviewer to point out edge cases.

Code with confidence once you understand. The algorithm is actually quite simple once you grasp it. Don't second-guess yourself. Write it cleanly, explain as you go, and trust the logic.

Key Takeaways

• Track a range (low to high) of possible unmatched opening parentheses instead of a single count; this captures all wildcard interpretations in one pass.
• Fail fast when high < 0 because no future character can recover from too many closing parentheses, but persist when low < 0 by resetting it to zero.
• The greedy O(n) time, O(1) space solution is strictly superior to brute force O(3^n) and stack-based O(n) space alternatives for this problem.
• The final validity check is low == 0, not high >= 0; the latter would incorrectly accept strings with unmatched opening parentheses.
• This range-tracking technique generalizes to any parsing problem where elements have multiple possible interpretations, from compiler design to configuration validators.

Real-World Applications

This pattern appears everywhere in production systems. Database query parsers handle nested subqueries with optional WHERE clauses using the same range-tracking principle. Regular expression engines face identical challenges with optional groups like (abc)?. Compiler parsers validate structure while handling optional elements like JavaScript's semicolons or TypeScript's type annotations.

I once debugged a mathematical expression parser that choked on implicit multiplication. Users could write 2(x+1) instead of 2*(x+1). The fix? This exact range-tracking approach, treating the missing operator as a wildcard.

Practice Extensions

Want to push further? Try handling multiple wildcard types where * can be ( or ), while ? can only be ) or empty. Or extend to mixed brackets with [], {}, and () simultaneously. These variations deepen your understanding of range tracking.

Solutions in Other Languages

Python Solution

Python's clean syntax makes the algorithm shine:

class Solution:
    def check_valid_string(self, s: str) -> bool:
        low = 0   # Minimum possible unmatched '('
        high = 0  # Maximum possible unmatched '('

        for ch in s:
            if ch == '(':
                low += 1
                high += 1
            elif ch == ')':
                low -= 1
                high -= 1
            else:  # ch == '*'
                low -= 1   # Treat as ')' for minimum
                high += 1  # Treat as '(' for maximum

            if high < 0:
                return False

            if low < 0:
                low = 0

        return low == 0

JavaScript Solution

JavaScript's modern ES6+ syntax with const/let and strict equality:

class Solution {
  checkValidString(s) {
    let low = 0;
    let high = 0;

    for (let i = 0; i < s.length; i++) {
      const ch = s[i];

      if (ch === '(') {
        low++;
        high++;
      } else if (ch === ')') {
        low--;
        high--;
      } else {  // ch === '*'
        low--;   // Treat as ')' for minimum
        high++;  // Treat as '(' for maximum
      }

      if (high < 0) {
        return false;
      }

      if (low < 0) {
        low = 0;
      }
    }

    return low === 0;
  }
}

C++ Solution

C++ with explicit types and STL:

class Solution {
public:
  bool checkValidString(std::string s) {
    int low = 0;
    int high = 0;

    for (int i = 0; i < s.length(); i++) {
      char ch = s[i];

      if (ch == '(') {
        low++;
        high++;
      } else if (ch == ')') {
        low--;
        high--;
      } else {  // ch == '*'
        low--;   // Treat as ')' for minimum
        high++;  // Treat as '(' for maximum
      }

      if (high < 0) {
        return false;
      }

      if (low < 0) {
        low = 0;
      }
    }

    return low == 0;
  }
};

Go Solution

Go's minimalist approach with := and no parentheses around conditions:

func (s *Solution) CheckValidString(str string) bool {
    low := 0
    high := 0

    for i := 0; i < len(str); i++ {
        ch := str[i]

        if ch == '(' {
            low++
            high++
        } else if ch == ')' {
            low--
            high--
        } else {  // ch == '*'
            low--   // Treat as ')' for minimum
            high++  // Treat as '(' for maximum
        }

        if high < 0 {
            return false
        }

        if low < 0 {
            low = 0
        }
    }

    return low == 0
}

Scala Solution

Scala's expressive for (i <- 0 until s.length) with implicit return:

class Solution {
  def checkValidString(s: String): Boolean = {
    var low = 0
    var high = 0

    for (i <- 0 until s.length) {
      val ch = s(i)

      if (ch == '(') {
        low += 1
        high += 1
      } else if (ch == ')') {
        low -= 1
        high -= 1
      } else {  // ch == '*'
        low -= 1   // Treat as ')' for minimum
        high += 1  // Treat as '(' for maximum
      }

      if (high < 0) {
        return false
      }

      if (low < 0) {
        low = 0
      }
    }

    low == 0
  }
}

Each language expresses the same elegant algorithm. Two counters, one pass, constant space. The core insight transcends syntax.

Conclusion

The wildcard parenthesis validator reveals a profound truth: sometimes the breakthrough isn't adding complexity but changing perspective. We transformed "Which exact interpretation is valid?" into "Could any interpretation be valid?" Two counters, one pass, linear time.

This pattern extends everywhere. Type inference tracks possible types. Query optimizers use bounds for cost estimates. Once you internalize range tracking, you'll spot it in countless algorithms.

Ready to develop this algorithmic intuition? Join over 50,000 developers on Firecode who have transformed their problem-solving abilities and landed roles at top tech companies. Master the fundamentals, conquer complex problems, and build your foundation for the next breakthrough.

Happy coding, and may all your wildcards find their perfect match! 🎯