The O(n) Club: Score of Parentheses—Where Mildly Annoying Brackets Become Mathematical Fireworks

The O(n) Club: Score of Parentheses—Where Mildly Annoying Brackets Become Mathematical Fireworks

⚡ TL;DR

Don’t (re)curse yourself! You can score a parentheses string in O(n) with a friendly depth counter. Every () gets you big points depending how deep it is—think video game powerup in a Russian doll. Quick Java cheat:

// Stack-free scoring in Java
int scoreOfParentheses(String s) {
    int score = 0, depth = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s.charAt(i) == '(') depth++;
        else {
            depth--;
            if (s.charAt(i-1) == '(') score += 1 << depth;
        }
    }
    return score;
}

🧠 How Devs Usually Mess This Up

First instinct: recursively chop the string like a chef losing control of the onion dicer. Or, treat every parenthesis as if it brings a math operator to the party alone—leads to either an O(n^2) catastrophe or a truly tragic result. Reminder: brute force and substring slicing are harder to debug than a mutex at 3am.

🔍 What’s Actually Going On

Imagine bracket land like an old-school arcade. Whenever you close a simple ()—and it’s buried under five layers of parentheses—YOU, my friend, just hit a 2⁴ combo. Each layer doubles the loot. Scan each character, track your nesting level, and light up the score whenever () is completed. Or, try a stack if you want nostalgia for compilers… and hand cramps.

🛠️ PseudoCode

• Initialize score, depth = 0.
• For each char in the string:
• If it’s '(', bump up depth.
• If it’s ')', drop depth.
• If you just closed a (), add 1 << depth (a.k.a 2^depth) to score.
• Return score and treat yourself to a bug-free coffee.

💻 The Code

// Fast and readable Java stackless approach
public int scoreOfParentheses(String s) {
    int score = 0, depth = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            depth++;
        } else {
            depth--;
            if (s.charAt(i - 1) == '(') {
                score += 1 << depth;
            }
        }
    }
    return score;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Counting Too Early: Don’t add to score unless you just closed a pair, not after any random ‘)’.
• Depth Fumble: Update depth before scoring that power-of-two! Get this backwards and you’ll live in off-by-one limbo.
• Space & Time: Both stack and depth-only approaches are O(n) time. Use O(1) space if you like speed, O(n) with a stack if you’re feeling poetic.
• Boring Corner Cases: Empty string = zero. Nesting without pairs can’t happen—they promised balanced inputs for once.

🧠 Interviewer Brain-Tattoo

“In the land of balanced parentheses, only () at depth d gets to party with 2^d-1 points. Why? Because brackets are just fancier bits.”