A balanced string scores by three rules: `()` is 1, `AB` adds, and `(A)` doubles. Once you unfold that recursion, every point of the final score traces back to one specific thing — an innermost `()` pair — and the doubling just counts how many parentheses wrap it. So a pair nested under `d` other pairs is worth exactly `2^d`, and nothing else in the string contributes anything at all. My first instinct was the structural one: a stack of partial scores, push `0` on `(`, and on `)` pop and fold `max(2 * popped, 1)` into the new top. That is correct and it is what most people write. But it rebuilds the whole parse tree to answer a question that only depends on depth, and the balanced-string guarantee means the tree was never in doubt. ## Worked example `s = "(()(()))"`. Walk it with a depth counter, and only react when a `)` closes immediately after a `(`: - `i=0 '('` → depth 1 - `i=1 '('` → depth 2 - `i=2 ')'` → depth 1, and `s[1]` is `(`, so this is an innermost pair → add `1 << 1 = 2` - `i=3 '('` → depth 2 - `i=4 '('` → depth 3 - `i=5 ')'` → depth 2, `s[4]` is `(` → add `1 << 2 = 4` - `i=6 ')'` → depth 1, `s[5]` is `)` → nothing - `i=7 ')'` → depth 0, `s[6]` is `)` → nothing Total 6. The rules agree: the outer pair wraps `()(())`, which is `1 + 2 = 3`, doubled to 6. ## Complexity - **Time** O(n) — a single left-to-right scan, one comparison per character. - **Space** O(1) — two integers, no stack. ## Code (C++) ```cpp class Solution { public: int scoreOfParentheses(string s) { int ans = 0, depth = 0; for (int i = 0; i < (int)s.size(); ++i) { if (s[i] == '(') { ++depth; } else { --depth; if (s[i - 1] == '(') ans += 1 << depth; } } return ans; } }; ``` ## One note The order inside the `else` branch is the whole trick, and it is easy to flip. You must decrement `depth` *before* reading `1 << depth`. At the moment you see the `)` of an innermost pair, `depth` still counts that pair itself; the exponent you want is the number of pairs *around* it, which is one less. Add first and every score comes out doubled. Two smaller things worth keeping. `s[i - 1]` is never out of bounds, because a guaranteed-balanced string cannot open with `)` — the first character is always `(`, so the first time you take this branch `i` is at least 1. And `1 << depth` is safe in a plain `int` only because the constraints cap the length at 50, putting max depth at 25; on a longer input that shift is a silent overflow waiting to happen, and I would want a `long long` or an explicit depth bound before trusting it. The transferable idea: when a recursive definition only ever multiplies by a constant on the way down, you can usually drop the recursion and count the exponent instead.