Score of Parentheses
Medium · Stack & Strings · String · Stack
Problem
You are given a balanced string s of parentheses. Its score follows three rules:
- "()" scores 1;
- two balanced strings written one after the other, AB, score A + B;
- a balanced string wrapped in a pair, (A), scores 2 · A.
Return the score of s.
Examples
Input: s = "(()())" Output: 4
The inside ()() scores 1 + 1 = 2, and the wrapper doubles it to 4.
Input: s = "()(())" Output: 3
() scores 1 and (()) scores 2 · 1 = 2, so 3 in all.
Input: s = "()" Output: 1
The base rule: 1.
Constraints
- 2 <= s.length <= 50
- s contains only '(' and ')'
- s is balanced
Approaches
- Baseline: recurse on the top-level parts — time O(n²), space O(n)
Follow-up
The depth scan uses O(1) memory. A stack of partial scores gives the same answer in one pass too: push 0 on (, and on ) pop v and add max(2 · v, 1) to the new top. The use cases change the doubling factor and ask for the score of every top-level part.
Related problems
Start free on Cariara · Coding problems · System design studio
