526. Score of Parentheses
You are given a balanced parentheses string s — every opening bracket has a matching closing bracket, and the string contains nothing else. Its score is defined by three rules:
- a bare pair
()is worth1, - two balanced strings written side by side,
AB, are worthscore(A) + score(B), - wrapping a balanced string in a pair,
(A), doubles it:2 * score(A).
Given s, return its score as an integer.
Example 1:
Input: s = "(())"
Output: 2
Explanation: The inner () is worth 1, and the surrounding pair doubles it to 2.
Example 2:
Input: s = "()()"
Output: 2
Explanation: Two bare pairs side by side: 1 + 1 = 2.
Example 3:
Input: s = "(()(()))"
Output: 6
Explanation: Inside the outer pair sits () worth 1 next to (()) worth 2, totalling 3; the outer pair doubles that to 6.
Constraints:
- 2 ≤ s.length ≤ 50
- s consists only of the characters '(' and ')'
- s is a balanced parentheses string
Hints:
Work with a stack of partial scores: an opening bracket starts a fresh group whose score you don't know yet; a closing bracket finishes the most recent group.
On '(' push a 0. On ')' pop the finished group's score v: the completed group is worth 1 if v == 0 (it was a bare pair) and 2 * v otherwise — then add that onto the new top of the stack.
For O(1) space, notice that only bare pairs create value; everything else just doubles. A () nested inside d outer pairs contributes exactly 2^d, so one pass tracking the current depth is enough.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "(())"
Expected output: 2