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 ✓

Depth trick for s = "(()(()))":

Chars: ( ( ) ( ( ) ) ) Depth: 1 2 1 2 3 2 1 0

When ) follows (:

• Index 2: ')' and s[1]='(' → depth=1 → add 2^1 = 2... wait, depth should be the depth of the () pair.

Let me redo: track depth as we scan; decrement before checking.

i=0 '(' depth: 0→1
i=1 '(' depth: 1→2
i=2 ')' prev='(' → depth: 2→1, add 2^1=2... 

Hmm, expected 6 not just 2 from first pair. Let me recheck with "(())":

• i=0 '(' depth 0→1
• i=1 '(' depth 1→2
• i=2 ')' prev='(' → 2→1, add 2^1=2. ans=2.
• i=3 ')' prev is '(' no, prev is ')' → no add.

ans = 2. Correct!

For `"(()(()))":

• i=0,1: depth reaches 2
• i=2: ')' prev='(' → depth=2→1, add 2^1=2. ans=2
• i=3,4: depth reaches 3
• i=5: ')' prev='(' → depth=3→2, add 2^2=4. ans=6
• i=6,7: ')' but prev was ')' at 5 and ')' at 6, no more atomic ()

Result: 6 ✓

Solution (Optimal)#

# Python — Stack approach: O(n) time, O(n) space
def scoreOfParentheses(s: str) -> int:
    stack = [0]  # start with a base scope score of 0
 
    for c in s:
        if c == '(':
            stack.append(0)  # open a new scope
        else:
            v = stack.pop()          # close the current scope
            # If v == 0, this was an empty (), scoring 1
            # If v > 0, this was (A), scoring 2*A
            stack[-1] += max(2 * v, 1)
 
    return stack[0]
 
 
# Python — Depth trick: O(n) time, O(1) space
def scoreOfParenthesesO1(s: str) -> int:
    ans = 0
    depth = 0
 
    for i, c in enumerate(s):
        if c == '(':
            depth += 1
        else:
            depth -= 1
            # A ')' that immediately follows '(' is an atomic "()"
            # It contributes 2^depth (depth after decrement = nesting level of the pair)
            if s[i - 1] == '(':
                ans += 1 << depth  # equivalent to 2^depth
 
    return ans

// JavaScript — Stack approach: O(n) time, O(n) space
function scoreOfParentheses(s) {
    const stack = [0];
 
    for (const c of s) {
        if (c === '(') {
            stack.push(0);
        } else {
            const v = stack.pop();
            stack[stack.length - 1] += Math.max(2 * v, 1);
        }
    }
 
    return stack[0];
}
 
// JavaScript — Depth trick: O(n) time, O(1) space
function scoreOfParenthesesO1(s) {
    let ans = 0;
    let depth = 0;
 
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            depth++;
        } else {
            depth--;
            if (s[i - 1] === '(') {
                ans += 1 << depth;  // 2^depth
            }
        }
    }
 
    return ans;
}

Complexity:

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.