Score of Parentheses — Stack-Based Scoring (LeetCode 856)

Score of Parentheses (LeetCode 856) combines parentheses matching with arithmetic. The stack doesn’t just track brackets — it tracks scores at each nesting depth.

The Problem

Given a balanced parentheses string s, compute its score based on:

Rule	Example	Score
() is 1	()	1
(A) is 2 * A	(())	2
AB is A + B	()()	2

More examples:

"(())"       → 2 * 1 = 2
"()()"       → 1 + 1 = 2
"(()(()))"   → 2 * (1 + 2*1) = 2 * 3 = 6

Stack Approach — The Key Idea

Use a stack where each entry represents the running score at that nesting depth. When you see (, push a new scope (0). When you see ), pop the scope, compute its score, and add it to the parent scope.

The formula on closing:

• Pop the top value v
• The scope’s score is max(2 * v, 1) — this handles both () (empty scope = 1) and (A) (double the inner score)
• Add this score to the new top of the stack (the parent scope)

Python Implementation

def score_of_parentheses(s):
    """
    Stack-based scoring of balanced parentheses.
    Time: O(n) — single pass through the string.
    Space: O(n) — stack depth up to n/2.
    """
    stack = [0]  # base scope

    for char in s:
        if char == '(':
            stack.append(0)  # new scope with score 0
        else:
            v = stack.pop()
            # () = 1, (A) = 2*A
            score = max(2 * v, 1)
            stack[-1] += score

    return stack[0]

Step-by-Step Trace

Trace for s = "(()(()))":

Start:         stack = [0]

char '(':      push 0          stack = [0, 0]
char '(':      push 0          stack = [0, 0, 0]
char ')':      pop 0
               score = max(2*0, 1) = 1
               stack[-1] += 1   stack = [0, 1]
char '(':      push 0          stack = [0, 1, 0]
char '(':      push 0          stack = [0, 1, 0, 0]
char ')':      pop 0
               score = max(2*0, 1) = 1
               stack[-1] += 1   stack = [0, 1, 1]
char ')':      pop 1
               score = max(2*1, 1) = 2
               stack[-1] += 2   stack = [0, 3]
char ')':      pop 3
               score = max(2*3, 1) = 6
               stack[-1] += 6   stack = [6]

Answer: 6 ✓

Alternative: Depth-Based O(1) Space

There is a clever O(1) space trick. Every () pair at depth d contributes 2^d to the total score. You only add a score when you see ) immediately after (.

def score_of_parentheses_depth(s):
    """
    Depth-based approach — O(1) space.
    Each () at depth d contributes 2^d.
    """
    depth = 0
    score = 0

    for i, char in enumerate(s):
        if char == '(':
            depth += 1
        else:
            depth -= 1
            if s[i - 1] == '(':
                # This is a () pair at current depth
                score += 1 << depth  # 2^depth

    return score

Why does this work?

Consider (()(())):

• The first () is at depth 2 → contributes 2^2 = 4? No, let’s recount.
• Actually at depth 1 after the outer ( opens → wait, let me re-derive.

After the outer (, depth = 1. After the second (, depth = 2. The first ) closes at depth 2, and since s[i-1] = '(', it is a () leaf. At this point depth has already decremented to 1, so contribution = 2^1 = 2.

The second () is at depth 2 inside (()), so after decrementing depth is 2, contribution = 2^2 = 4? Let me trace carefully:

(  (  )  (  (  )  )  )
d: 1  2  1  2  3  2  1  0

At i=2, ')' after '(': depth=1, score += 2^1 = 2
At i=5, ')' after '(': depth=2, score += 2^2 = 4

Total = 2 + 4 = 6 ✓

Comparison of Approaches

Approach	Time	Space	Complexity
Stack	O(n)	O(n)	Easy to understand
Depth counting	O(n)	O(1)	Tricky but elegant

Edge Cases

1. Simplest case — "()" → 1
2. Deeply nested — "(((())))" → 8 (2^3)
3. Flat concatenation — "()()()" → 3
4. Mixed — "(()())" → 2*(1+1) = 4
5. Maximum depth — score grows exponentially with nesting

Common Mistakes

• Forgetting the base scope: initialize stack with [0], not []
• Using 2 * v without the max: an empty pair () would score 0 instead of 1
• Off-by-one in depth counting: remember depth is decremented before you use it

When to Use This Pattern

Use this stack-scoring technique when:

• You need to compute a recursive score based on nesting structure
• The problem has rules like “inner content is multiplied, siblings are added”
• You are parsing nested expressions with aggregation

Related Problems

Problem	Difficulty	Key Idea
LeetCode 856 — Score of Parentheses	Medium	This problem
LeetCode 20 — Valid Parentheses	Easy	Stack-based matching
LeetCode 1190 — Reverse Substrings Between Parentheses	Medium	Stack with string ops
LeetCode 394 — Decode String	Medium	Nested multiplier pattern

Key Takeaway

Score of Parentheses teaches you to use the stack as a scope tracker — each stack entry represents the accumulated score at a nesting level. This pattern extends to any problem where nested structures produce recursive computations.