Bracket Score

MediumStack

Problem

A balanced string s of ( and ) is scored by three rules:

- () scores 1; - two balanced strings side by side, AB, score score(A) + score(B); - a balanced string wrapped in a pair, (A), scores 2 · score(A).

Return the score of s.

Example 1

Input:
s = "(()(()))"
Output:
6

Inside the outer pair: () scores 1 and (()) scores 2, so 3; wrapping doubles it to 6.

Example 2

Input:
s = "()()"
Output:
2

Constraints

  • 2 ≤ s.length ≤ 50
  • s is balanced and non-empty

Hint

Show the first hint

Each '(' opens a new context whose score you will compute; ')' finishes it. Where do you keep unfinished contexts?

Walkthrough

How to approach it

01Clarify before coding

  • Is the input always balanced? Yes.
  • How big can the score get? Length ≤ 50 means at most 2^24, which fits easily.

02Brute force

Recursively split s into top-level groups; for each group recurse on its interior and apply the rules.

Cost: Finding split points by rescanning costs O(n) per level: O(n²) overall for deep nests.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.