Score of Parentheses: Stack-Based Scoring of Nested Brackets

Score of Parentheses is LeetCode problem 856, rated Medium. Given a balanced parentheses string s, you need to compute its score based on a recursive set of rules. It is a satisfying problem because the rules are simple, but translating them into a clean algorithm requires thinking carefully about how nesting maps to multiplication.

The problem

You are given a balanced parentheses string s (every ( has a matching )). Compute its score according to these three rules:

1. () has score 1
2. (A) has score 2 * A, where A is a balanced substring
3. AB has score A + B, where A and B are balanced substrings placed side by side

Examples:

• "()" returns 1 (rule 1)
• "(())" returns 2 (rule 2: the inner () scores 1, wrapping it doubles to 2)
• "()()" returns 2 (rule 3: two adjacent () each score 1, sum is 2)
• "(()(()))" returns 6 (nested: inner scores are 1 and 2, summed to 3, doubled by the outer parens to 6)

The brute force approach

One way to solve this is recursion. You can parse the string like a grammar: find matching pairs, recurse on the contents, and apply the scoring rules. For adjacent groups, find where each balanced group ends and sum their scores.

This works, but it requires careful index tracking to find where each group starts and ends. In the worst case, you might re-scan parts of the string multiple times. It is correct, but there is a much cleaner approach.

The key insight

Instead of parsing the string recursively, you can use a stack of scores. The idea is that each nesting level has its own running total. When you see (, you push a 0 to start a fresh score for that level. When you see ), you pop the top, compute the score for the group you just closed, and add it to the level above.

Here is the rule for computing the score when you close a group:

• If the popped value is 0, this was a bare (), which scores 1
• If the popped value is greater than 0, it had nested content, so the score is 2 * popped

In both cases, you can write this as max(2 * popped, 1).

You add that result to the new top of the stack, which represents the score being accumulated at the enclosing level.

Step-by-step walkthrough

Let's trace through "(()(()))" using the stack approach. We start with stack = [0] as a base accumulator.

Notice the pattern: every ( pushes a 0, every ) pops and scores. The stack never holds more entries than the maximum nesting depth plus one. By the end, the single remaining value on the stack is your answer.

The code

Here is the Python solution using the stack approach:

def scoreOfParentheses(s: str) -> int:
    stack = [0]

    for ch in s:
        if ch == "(":
            stack.append(0)
        else:
            popped = stack.pop()
            stack[-1] += max(2 * popped, 1)

    return stack[0]

The entire algorithm is five lines of logic. For each (, push a new 0. For each ), pop the inner score, convert it using max(2 * popped, 1), and add to the enclosing level. When the loop finishes, stack[0] holds the total score.

Complexity analysis

Stack-based time: O(n). You process each character exactly once. Each character causes at most one push or one pop, both O(1) operations.

Stack-based space: O(n). In the worst case (e.g., "(((())))" with deep nesting), the stack grows proportional to the nesting depth, which can be up to n/2.

The depth-counting approach

There is an elegant O(1) space alternative. The observation is that only the innermost () pairs contribute to the score. Each bare () contributes 2^depth to the total, where depth is how many layers of outer parentheses wrap around it.

def scoreOfParentheses(s: str) -> int:
    depth = 0
    score = 0

    for i in range(len(s)):
        if s[i] == "(":
            depth += 1
        else:
            depth -= 1
            if s[i - 1] == "(":
                score += 1 << depth

    return score

When you see ) right after (, you have found a leaf (). Its contribution is 2^depth (after decrementing depth for the closing paren). All the doubling from outer layers is captured by the power of 2. Adjacent groups at the same depth naturally sum together.

The building blocks

This problem is built from reusable patterns that appear across many LeetCode problems.

Stack as a nesting tracker

The idea of using a stack to track nesting depth shows up whenever you need to process hierarchically structured input. Each time you "enter" a level, you push. Each time you "exit," you pop and combine with the level above. You will see the same structure in:

• Basic Calculator (LeetCode 224): push the running result and operator when you see (, pop and combine when you see )
• Decode String (LeetCode 394): push the current string and multiplier at [, pop and concatenate at ]
• Flatten Nested List Iterator (LeetCode 341): use a stack to walk through nested list structures

Score accumulation on pop

The pattern of computing a value when you pop (rather than when you push) is a common stack technique. You defer the calculation until you have all the information you need. In this problem, you do not know the inner score until you reach the matching ). The same deferred-computation pattern appears in expression evaluation, histogram problems, and tree serialization.

Edge cases

These are the inputs to watch for:

• Single pair ("()"). The simplest case. Push 0, pop 0, max(0, 1) = 1. Return 1.
• Deep nesting ("(((())))"). Each ) doubles the score. The innermost () scores 1, and three layers of wrapping give 2 * 2 * 2 * 1 = 8.
• All adjacent ("()()()"). Three pairs at the same level. Each scores 1, and they sum to 3.
• Mixed nesting and adjacency ("(()(()))"). The example from our walkthrough. Inner scores of 1 and 2 sum to 3, then the outer parens double to 6.
• Two-level nesting ("(())"). One layer of wrapping around (). Score is 2 * 1 = 2.

From understanding to recall

You understand how the stack accumulates scores at each nesting level. You see why max(2 * popped, 1) handles both bare pairs and nested content. You know the depth-counting alternative exists.

But can you write either solution from scratch in under two minutes? The details trip people up. Do you initialize the stack with [0] or []? Do you multiply before or after adding to the top? Is it max(2 * popped, 1) or 2 * max(popped, 1)? These are small things, but they matter.

Spaced repetition turns understanding into automatic recall. You type the solution from memory, check it, and repeat at increasing intervals. After a few rounds, the initialization, the pop logic, and the scoring formula become second nature. You write them without pausing to reconstruct the reasoning.

Related posts

• Valid Parentheses - The foundational stack-matching problem. Score of Parentheses extends the same push/pop pattern by computing scores instead of just checking validity.
• Generate Parentheses - Builds valid parentheses strings using backtracking. A construction problem from the same parentheses family.
• Longest Valid Parentheses - Finds the longest valid substring using index-based stack tracking. Another way stacks solve parentheses problems beyond simple matching.