Score of Parentheses LeetCode 856

LeetCode 856 — Score of Parentheses — gives you a balanced parentheses string s. The score is defined recursively: () has score 1, AB (two balanced strings concatenated) has score A + B, and (A) (a balanced string wrapped in parentheses) has score 2 * A.

For example, "(())" scores 2 because the inner "()" scores 1, and wrapping it gives 2*1 = 2. The string "(()(()))" scores 2*(1 + 2*1) = 2*3 = 6. Each nesting level doubles the score, while concatenation adds scores together.

This problem has three elegant solutions: a stack-based approach, a depth-counting approach, and a divide-and-conquer approach. The depth-counting method is the most insightful — it recognizes that only the leaf "()" pairs contribute to the score, each contributing 2^depth.

Maintain a stack of integers representing the running score at each nesting depth. Start with a stack containing just [0] (the score at depth 0). When you encounter an open parenthesis, push 0 onto the stack — this starts a new score accumulator for the deeper level.

When you encounter a close parenthesis, pop the top value v. If v is 0, this closes a leaf "()" pair, so the score is 1. Otherwise this closes a "(A)" wrapper, so the score is 2*v. Add this score to the new top of the stack, which represents the enclosing level.

After processing the entire string, the stack contains a single element: the total score. This approach directly mirrors the recursive definition: opening a parenthesis enters a new subproblem, closing it resolves the subproblem and merges the result upward.

The key insight is that only leaf "()" pairs contribute to the final score. Every leaf at depth d contributes exactly 2^d to the total. Non-leaf parentheses just multiply — they never add new score, they only scale existing scores by powers of 2.

Track the current depth with a single integer. On "(", increment depth. On ")", decrement depth. If the current ")" immediately follows a "(", this is a leaf — add 2^depth to the result (note: depth was already decremented, so 2^depth gives the correct power).

This approach uses O(1) space (just depth and result) and O(n) time. It is the most elegant solution because it cuts through the recursive structure to identify the fundamental quantity: each leaf's contribution is determined entirely by its nesting depth.

Consider s = "(()(()))". Stack approach: start [0]. Index 0 "(": push 0 → [0,0]. Index 1 "(": push 0 → [0,0,0]. Index 2 ")": pop 0, leaf, add 1 to top → [0,1]. Index 3 "(": push 0 → [0,1,0].

Index 4 "(": push 0 → [0,1,0,0]. Index 5 ")": pop 0, leaf, add 1 → [0,1,1]. Index 6 ")": pop 1, non-leaf, add 2*1=2 → [0,3]. Index 7 ")": pop 3, non-leaf, add 2*3=6 → [6]. Answer: 6.

Depth approach: index 0 "(" depth=1. Index 1 "(" depth=2. Index 2 ")" depth=1, prev was "(" so leaf: result += 2^1 = 2. Index 3 "(" depth=2. Index 4 "(" depth=3. Index 5 ")" depth=2, leaf: result += 2^2 = 4. Index 6 ")" depth=1, not leaf. Index 7 ")" depth=0, not leaf. Total: 2+4 = 6.

Python stack version: stack = [0]. For each char, if "(": stack.append(0). Else: v = stack.pop(); stack[-1] += max(2*v, 1). Return stack[0]. The max(2*v, 1) handles both leaf (v=0 → 1) and non-leaf (v>0 → 2*v) cases in one expression.

Python depth version: depth = result = 0. For i, c in enumerate(s): if c == "(": depth += 1, else: depth -= 1, and if s[i-1] == "(": result += 1 << depth. Return result. The bit shift 1 << depth computes 2^depth efficiently.

Java implementations follow the same logic. Use a Deque<Integer> for the stack version. For the depth version, use a simple int depth and int result with the same leaf-detection check s.charAt(i-1) == '('.

Both approaches run in O(n) time where n is the string length. The stack approach does one push or pop per character. The depth approach does one increment or decrement per character plus one comparison.

Space complexity: the stack approach uses O(n/2) = O(n) space in the worst case (deeply nested string like "(((())))"). The depth counter approach uses O(1) space — just two integer variables.

The depth approach is strictly better in space while matching the stack approach in time. In interviews, present the stack solution first (more intuitive), then optimize to the depth counter (shows deeper insight into the problem structure).

Valid Parentheses (LeetCode 20) is the foundation — just check if parentheses are balanced using a stack. Score of Parentheses builds on this by computing a value rather than a boolean. Both use the same stack mechanics.

Longest Valid Parentheses (LeetCode 32) finds the longest balanced substring. It uses a stack with indices rather than values. Together with Score of Parentheses, these three problems cover the full range of parentheses stack problems on LeetCode.

Generate Parentheses (LeetCode 22) is a complementary backtracking problem that generates all balanced strings of length 2n. Understanding the scoring rules from this problem helps verify generated strings — a useful cross-reference during interview practice.