Nested Bracket Score Calculation

Medium20–25 min

Topics

StackStringRecursion

Companies

GoogleAmazon

Given a balanced bracket string s containing only '(' and ')', compute its score using these rules: "()" scores 1; two concatenated pieces AB score the sum of their individual scores; and a piece wrapped as (A) scores twice A — nesting doubles whatever score is inside. Since nesting always doubles and concatenation always adds, every innermost "()" pair's ultimate contribution to the total is exactly 2^d, where d is how many enclosing pairs wrap around it. A single pass with a stack computes this without ever explicitly calculating a power of 2: push a fresh 0 for every new level opened, and whenever a level closes, fold its score into the level directly beneath it — doubling it first if it wasn't just a bare pair. By the time the string is fully consumed, the bottom of the stack holds the total.

Test Case 1:

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

Output:3

Explanation:"(())" scores 2 (a pair nested one level deep doubles the base score of 1), and the trailing "()" scores 1 — concatenated pieces add: 2 + 1 = 3.

Test Case 2:

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

Output:4

Explanation:Three levels of nesting: the innermost "()" scores 1, doubled by each enclosing pair — 1 → 2 → 4.

Test Case 3:

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

Output:3

Explanation:"()" scores 1 and "(())" scores 2, concatenated: 1 + 2 = 3.

Constraints

◆1 ≤ s.length ≤ 20
◆s is a balanced bracket string consisting only of '(' and ')'

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Depth-Count Every Matched Pair

Brute

Every innermost "()" pair contributes 2^d to the total score, where d is how many levels of nesting enclose it — and every score in this problem ultimately traces back to summing that contribution over each such pair (concatenation just adds scores, nesting just doubles them). So: scan for every adjacent "()" pair in the string, and for each one, count its nesting depth by re-scanning everything before it and tracking the running balance of unmatched '(' versus ')'. Sum 2^depth over every pair found. Correct, but re-scanning from the start for every pair costs O(n) each, and there can be up to n/2 pairs — O(n²) total.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int scoreOfBrackets(String s) {
        int total = 0;
        int n = s.length();
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == '(' && s.charAt(i + 1) == ')') {
                int depth = 0;
                for (int k = 0; k < i; k++) {
                    if (s.charAt(k) == '(') depth++;
                    else depth--;
                }
                total += 1 << depth;
            }
        }
        return total;
    }
}

Optimal — Single Pass With a Stack of Partial Scores

Optimal

Track the running score at each nesting level on a stack, seeded with a 0 at the bottom for the outermost level. On '(', push a fresh 0 — a new level starts with no score yet. On ')', pop the just-finished level's score: if it was 0 (nothing accumulated inside), this was an innermost "()" pair, worth 1; otherwise, double whatever accumulated inside it (nesting doubles). Either way, add that value into the level directly below, which is now back on top of the stack. One pass, one push or pop per character — no re-scanning.

TimeO(n)

SpaceO(n)