The O(n) Club: Valid Parenthesis String — Greedy for Sanity, Wild About Wildcards

The O(n) Club: Valid Parenthesis String — Greedy for Sanity, Wild About Wildcards

⚡ TL;DR

This interview classic wants you to check if a string of ‘(‘, ‘)’, and ‘*’ (the wildcard that’s more indecisive than you at a buffet) can be a valid parenthesis string. Brute force makes your laptop boil; the greedy approach keeps you and your hardware alive. Behold, sanity in Java:

// Fast O(n) greedy solution
public boolean checkValidString(String s) {
    int minOpen = 0, maxOpen = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') { minOpen++; maxOpen++; }
        else if (c == ')') { minOpen--; maxOpen--; }
        else { minOpen--; maxOpen++; } // '*' is wild
        if (maxOpen < 0) return false;
        if (minOpen < 0) minOpen = 0;
    }
    return minOpen == 0;
}

🧠 How Devs Usually Mess This Up

If you think ‘*’ just means “skip me!”, or you start branching for each ‘*’ possibility, congrats: you’ve invented lag and pain. Trying every combination? Your code’s time complexity goes from “hobbyist” to “help desk ticket.” Even better: try a stack, and quickly find yourself in “wildcard juggling” hell—classic stacks never learned to improvise.

🔍 What’s Actually Going On

Picture ‘*’ as your office intern: sometimes helpful, sometimes missing, sometimes just making things complicated. Instead of panicking, just keep track of a range — from minimum to maximum possible open parentheses. Each ‘(‘ bumps both up. Each ‘)’ dings both down. Each ‘*’? Well, it could be ‘(‘, or ‘)’, or just nothing, so min goes down (maybe it’s a ‘)’), max goes up (maybe it’s a ‘(‘), and you pray neither counter breaks the rules. If maxOpen drops below zero, you’ve officially closed more than you ever opened—party’s over, return false.

🛠️ PseudoCode

• Initialize minOpen = 0; maxOpen = 0
• For each character:
• ‘(‘ → minOpen++, maxOpen++ (invite to open-party)
• ‘)’ → minOpen--, maxOpen-- (closing time!)
• ‘*’ → minOpen--, maxOpen++ (because it might be anything…or nothing)
• If maxOpen < 0, immediately fail (too many closes)
• Clamp minOpen at 0 (can’t have fewer than zero opens!)
• After the loop: if minOpen == 0, string can be valid. If not, the wildcards let you down.

💻 The Code

public boolean checkValidString(String s) {
    int minOpen = 0;
    int maxOpen = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            minOpen++;
            maxOpen++;
        } else if (c == ')') {
            minOpen--;
            maxOpen--;
        } else { // c == '*'
            minOpen--;
            maxOpen++;
        }
        if (maxOpen < 0) {
            return false;
        }
        if (minOpen < 0) {
            minOpen = 0;
        }
    }
    return minOpen == 0;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All stars, no structure: A string with a gazillion ‘*’s is technically valid, but don’t be lazy—let the logic prove it.
• Resetting minOpen to zero (not negative): Remember, you can’t have negative open parentheses. This is code, not quantum mechanics.
• Stack-based nostalgia: Don’t dust off that old paren stack. ‘*”s will have it panic and drop boxes everywhere.
• Time/Space complexity: O(n) time, O(1) space. The algorithm is so efficient, your laptop fan might even thank you.

🧠 Interviewer Brain-Tattoo

“Wildcards are fun… until you realize recursion is the new semicolon. Track the possibilities, not the panic.”