L11. Valid Parenthesis String | Multiple Approaches

A comprehensive guide to solving the Valid Parenthesis String problem using Greedy Algorithms, moving from brute-force recursion and dynamic programming to an optimal linear-time range-tracking approach.

1. Problem Statement & Definition of Validity

We are given a string containing three types of characters:

1. Opening parenthesis: (
2. Closing parenthesis: )
3. Asterisk: *

Our task is to determine whether the given string is a Valid Parenthesis String.

Definition of Validity

• Every opening parenthesis ( must have a corresponding closing parenthesis ).
• The opening parenthesis ( must always appear before its corresponding closing parenthesis ).
• The asterisk * is a wildcard character that can act as:
  • An opening parenthesis (
  • A closing parenthesis )
  • An empty character ("")

Example Validations

• () $\rightarrow$ Valid (Direct match)
• (*) $\rightarrow$ Valid (* can be evaluated as an empty character "")
• (*)) $\rightarrow$ Valid (* can be evaluated as ( to match the first ))
• )* $\rightarrow$ Invalid (Closing parenthesis appears before any opening parenthesis)

2. Core Mental Model: The Simple Parenthesis Case (No Asterisks)

Before handling the wildcard *, let us analyze how we validate a string containing only standard parentheses ( and ).

Naive Counter Approach

We initialize a count variable at 0:

• Encounter ( $\rightarrow$ Increment count (count++)
• Encounter ) $\rightarrow$ Decrement count (count--)
• End Condition: If count == 0 at the end of the string, it is valid.

Real-Life Analogy: The Receptionist and Tickets

Note: Imagine a ticketing booth where every opening parenthesis ( hands out a ticket, and every closing parenthesis ) collects a ticket. If a customer tries to hand in a ticket ) when the booth has zero tickets, or if the booth still holds uncollected tickets at the end of the day, the workflow fails.

Edge Case: Premature Underflow

Consider the string )(:

Rule: At any point during traversal, if count drops below 0, the string is immediately invalid. We must stop and return false instantly.

3. The Brute Force Approach: Exploring All Asterisk Combinations

Because the asterisk * can represent three different characters ((, ), or empty), a brute-force recursive strategy explores every possible interpretation branch.

Recursive Branching Workflow

Recursive Java-Style Pseudo-Code

boolean isValid(String s, int index, int count) {
    // Base Case 1: Count dropped below zero (Invalid path)
    if (count < 0) return false;
    
    // Base Case 2: Reached end of string
    if (index == s.length()) {
        return count == 0;
    }
    
    char ch = s.charAt(index);
    
    if (ch == '(') {
        return isValid(s, index + 1, count + 1);
    } else if (ch == ')') {
        return isValid(s, index + 1, count - 1);
    } else {
        // Asterisk branching: Try all 3 possibilities
        boolean op1 = isValid(s, index + 1, count + 1); // Treat as '('
        boolean op2 = isValid(s, index + 1, count - 1); // Treat as ')'
        boolean op3 = isValid(s, index + 1, count);     // Treat as empty
        
        return op1 || op2 || op3;
    }
}

Complexity Analysis of Brute Force

• Time Complexity: $\mathcal{O}(3^n)$ in the worst-case scenario (where every character is an asterisk, generating 3 branches per character).
• Space Complexity: $\mathcal{O}(n)$ auxiliary stack space corresponding to the depth of the recursive call stack.

4. Dynamic Programming Optimization (Memoization)

Because subproblems overlap when traversing indices with varying counts, we can optimize the recursive solution using Memoization (Dynamic Programming).

State Variables

• index: Ranges from 0 to N
• count: Ranges from 0 to N

5. The Optimal Greedy Approach: Range Tracking (Min & Max)

Instead of tracking an exact count or branching into exponential paths, we can maintain a range of possible open parenthesis counts using two variables: min and max.

• min: The minimum number of open parentheses ( that must be unmatched at the current state.
• max: The maximum number of open parentheses ( that could be unmatched at the current state.

How Asterisks Affect the Range

When we encounter an asterisk *, it widens our possible range:

1. As a closing parenthesis ): Decrements both min and max.
2. As an empty character (""): Keeps min and max unchanged.
3. As an opening parenthesis (: Increments both min and max.

Thus, for a single *, min decreases by 1 (or floors at 0), and max increases by 1.

6. Step-by-Step Execution Walkthrough

Let us trace the optimal greedy algorithm on the string: (*)

1. Initial State: min = 0, max = 0
2. Character ( (Index 0):
   • Opening parenthesis increments both bounds.
   • min = 1, max = 1
3. Character * (Index 1):
   • Asterisk acts as ) (min - 1), empty (min stays), or ( (max + 1).
   • Range shifts: min becomes $\max(0, 1 - 1) = 0$, max becomes $1 + 1 = 2$.
   • Current Range: [0, 2]
4. Character ) (Index 2):
   • Closing parenthesis decrements both bounds.
   • min becomes $\max(0, 0 - 1) = 0$, max becomes $2 - 1 = 1$.
   • Current Range: [0, 1]
5. Final Evaluation:
   • Loop completes. We check if min == 0. Since min is 0, a valid pairing configuration exists. Returns true.

7. Production-Ready Code Implementation (Java)

Here is the clean, decoupled, linear-time implementation of the optimal approach:

class Solution {
    public boolean checkValidString(String s) {
        int min = 0;
        int max = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            if (ch == '(') {
                min++;
                max++;
            } else if (ch == ')') {
                min--;
                max--;
            } else { // Character is '*'
                min--; // '*' acts as ')'
                max++; // '*' acts as '('
            }
            
            // If min drops below zero, correct it to zero (discard invalid negative counts)
            if (min < 0) {
                min = 0;
            }
            
            // If max drops below zero, it means we have more closing brackets than available '(' and '*' combined
            if (max < 0) {
                return false;
            }
        }
        
        // At the end, valid if the minimum required open brackets can be zero
        return min == 0;
    }
}

8. Summary and Key Takeaways

• Problem Core: Validating parenthesis strings with wildcards (*) requires accounting for multiple character interpretations.
• Brute Force Limitation: Exploring all combinations via recursion yields an exponential time complexity of $\mathcal{O}(3^n)$.
• DP Insight: Memoization reduces time to $\mathcal{O}(n^2)$, but is still suboptimal for strict interview standards.
• Greedy Range Paradigm: Tracking a dynamic range (min and max) allows us to manage wildcard branching without explicit recursion.
• Underflow Protection: Ensuring min floors at 0 discards impossible negative states immediately.
• Max Validation: If max drops below 0, closing brackets have overwhelmed all opening and wildcard options, triggering an immediate false.
• Final Check: The string is valid if and only if the minimum unmatched open bracket count min equals 0 at the end of traversal.
• Optimal Complexity: The greedy range-tracking algorithm achieves $\mathcal{O}(n)$ time complexity and $\mathcal{O}(1)$ auxiliary space complexity.