Score of Parentheses

Score of Parentheses

What is this problem about?

The Score of Parentheses interview question gives you a balanced string of parentheses and asks you to compute its "score." The scoring rules are: an empty pair () scores 1, and two consecutive scored strings AB score A + B, while a wrapped string (X) scores 2 * X. This is a stack-based parsing problem with a clean mathematical interpretation.

Why is this asked in interviews?

This problem is asked at Meta, Snap, TikTok, Google, and Bloomberg because it tests stack-based expression parsing — a core concept in compiler design, expression evaluation, and syntax analysis. The recursive scoring rules model a grammar, and the stack naturally handles the nested structure. It evaluates whether candidates can translate a recursive definition into an iterative stack solution.

Algorithmic pattern used

Two clean patterns: stack and bit manipulation. Stack approach: push 0 (current score) for each (. For ): pop the top score v. If v == 0, the current () pair scores 1 → add 1 to the new top. Otherwise, it's (X) → add 2*v to the new top. The final result is the sum of the stack. Bit-counting approach: for each (), the score contribution is 2^depth where depth is the nesting depth at that pair. Sum all () contributions.

Example explanation

Input: "(()(()))"

Stack approach:

• (: push 0. Stack: [0, 0].
• (: push 0. Stack: [0, 0, 0].
• ): pop 0 → v=0 → add 1 to top. Stack: [0, 1].
• (: push 0. Stack: [0, 1, 0].
• (: push 0. Stack: [0, 1, 0, 0].
• ): pop 0 → v=0 → add 1 to top. Stack: [0, 1, 1].
• ): pop 1 → v=1 → add 2*1=2 to top. Stack: [0, 3].
• ): pop 3 → v=3 → add 2*3=6 to top. Stack: [6].

Result: 6.

Common mistakes candidates make

• Not initializing the stack with a 0 before processing — the outermost level needs a base score.
• Confusing when to score 1 vs score 2*v — only () (with v=0) scores 1; a non-zero v means it's a wrapped group.
• Using recursion without memoization — the string has no overlapping subproblems to memoize.
• Misapplying the bit-counting approach by computing depth incorrectly.

Interview preparation tip

For the Score of Parentheses coding problem, the string and stack interview pattern is the primary approach. The bit-counting alternative is elegant: for each (), its contribution is 2^current_depth where depth is tracked by counting ( and ). Both approaches are O(n) time and O(n) or O(1) space respectively. Google and Bloomberg interviewers value the bit-counting approach for its O(1) space — mention it as an optimization after the stack solution.