Score of Parentheses — Stack Depth Doubling and O(1) Space

Problem Statement#

Given a balanced parentheses string s, return the score of the string based on the following rule:

• "()" has score 1.
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

Constraints:

• 2 <= s.length <= 50
• s consists of ( and ) only.
• s is a balanced parentheses string.

Input:  s = "()"
Output: 1

Input:  s = "(())"
Output: 2
Explanation: (()) = 2 * () = 2 * 1 = 2

Input:  s = "(()(()))"
Output: 6
Explanation: (()) = 2, () = 1, together = 3, so ((3)) = 6... actually:
(()(()))
= (()) + (()) is wrong, it's one big group
inner: () + (()) = 1 + 2 = 3, outer: (3) = 6

Why This Problem Matters#

LC 856 is a deceptively deep problem. The surface-level solution uses a stack (O(n) space), but the optimal solution uses a bit-shift depth trick that achieves O(1) space — and understanding why it works demonstrates real mathematical depth.

This problem tests: recursive nesting with a stack (same pattern as Decode String, LC 394), optimization from O(n) to O(1) space, and the insight that every () contributes 2^depth to the total score.

Companies: Google, Amazon. Often asked as a follow-up to Decode String (LC 394) or Valid Parentheses (LC 20) to test whether you can derive the mathematical shortcut.

The Core Insight#

Stack approach: Use a stack of running scores at each nesting level. On (, push 0 (start a new scope). On ), pop the scope's score v and add max(1, 2*v) to the parent scope: if v == 0 the scope contained () → score 1; otherwise it contained (A) → score 2*A.

Depth doubling insight (O(1) space): Every () at depth d contributes 2^d to the final score. Proof by induction: at depth 0, () = 1 = 2^0. At depth 1, (()) = 2*(()) = 2*1 = 2 = 2^1. At depth 2, ((())) = 4 = 2^2. Nested (A) simply adds one to the depth.

So: scan the string, tracking depth. Every time we see () (current char is ) and previous char was (), add 2^depth (or 1 << depth with bit shift) to the answer — where depth is the current depth before the closing paren.

This is a beautiful O(1) space solution that emerges from understanding the problem's mathematical structure.

Visual Dry Run#

Input: s = "(()(()))"

Stack approach:

Result: 6 ✓

The same answer without a stack#

Every () pair contributes 2^(d-1), where d is the depth that pair sits at. Nothing else in the string contributes anything, because (A) only ever doubles what is inside it. So one counter and one pass are enough.

Track the depth as you scan, and whenever a ) closes immediately after a (, add 2^(depth - 1) using the depth before the closing bracket drops it.

For s = "(()(()))":

Total 6, matching the stack version. The two ) that close a ) rather than a ( add nothing: they are the outer brackets whose doubling is already baked into the exponents.

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        score = depth = 0
        for i, ch in enumerate(s):
            if ch == '(':
                depth += 1
            else:
                depth -= 1
                if s[i - 1] == '(':      # a core "()" at this depth
                    score += 1 << depth
        return score

O(n) time and O(1) space, against O(n) space for the stack. Worth knowing, but say the stack version first in an interview — it is the one that generalises when the scoring rule changes.

Common Mistakes#

1. Stack approach: initializing stack to [] instead of [0]. The base score 0 at index 0 represents the outermost scope. Without it, adding max(2*v, 1) to stack[-1] on the first ) would fail.

2. Using 2*v when v == 0 (empty pair). When the scope's score is 0, we have an atomic () which scores 1, not 2 * 0 = 0. Always use max(2*v, 1).

3. Depth trick: forgetting to decrement depth before the check. The depth of the () pair is the depth after the closing ), not before. Decrement first, then add 1 << depth.

4. Depth trick: accessing s[i-1] when i == 0. The first character is always ( — it can never be ) that follows (, so i >= 1 is guaranteed when the condition fires. But always be mindful of index bounds.

5. Overflow with 1 << depth in Java/C++. The maximum depth is n/2 = 25. 1 << 25 = 33,554,432 — within 32-bit integer range. No overflow concern here, but in general be cautious with bit shifts.

Interview Tips#

• Present both solutions: "The stack approach is intuitive — I maintain a running score at each nesting level. The depth trick is the O(1) optimization: every atomic () at depth d contributes 2^d."
• Explain why max(2*v, 1): "If the scope had score 0 (empty), it was () which scores 1. If it had score v > 0, it was (A) which scores 2*A. The max handles both cases cleanly."
• For the depth insight: "The multiplication rule (A) = 2*A means each level of nesting doubles the contribution of the innermost (). An atomic () at depth d has been doubled d times → contributes 2^d."

Follow-up Questions#

1. Decode String (LC 394) — same stack save-and-restore pattern with repetition counts.
2. What if () scores 1 and (A) = A + 1? Rewrite the closing bracket case: stack[-1] += v + 1 instead of max(2*v, 1).
3. Can the depth trick be used for Decode String? Not directly — Decode String has explicit counts, so the depth alone is insufficient.
4. Minimum additions to make the score reach target T. Binary search or greedy on the structure.
5. Return the list of scores for each depth level. Extend the stack approach to track contributions per depth instead of summing.

Key Takeaways#

• Stack approach: push 0 on (; on ), pop scope score v and add max(2*v, 1) to the parent. max(2*v, 1) handles both () (score 1) and (A) (score 2*A).
• Depth trick (O(1) space): each atomic () at depth d contributes 2^d = 1 << depth to the total. Track depth with a counter; add 1 << depth whenever you see a ) that immediately follows (.
• The bit-shift insight emerges from the observation that (A) = 2*A is geometric doubling — an () at depth d has been doubled d times.
• Always initialize the stack with [0] — the base scope — not [].
• The max(2*v, 1) formula elegantly handles both the base case () and the recursive case (A) in one line.
• This problem rewards mathematical insight over brute-force stack simulation and is a good test of whether you can derive the O(1) optimization.