Skip to main content

856. Score of Parentheses

medium

Compute a score for a balanced parentheses string with nesting and concatenation rules. Two clean solutions: a stack of partial scores, and a counting trick with no stack at all.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a balanced parentheses string s, return the score of the string. The score of a balanced parentheses string is based on the following rule: '()' has score 1. AB has score A + B, where A and B are balanced parentheses strings. (A) has score 2 * A, where A is a balanced parentheses string.

Constraints

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

Examples

Example 1

Input
s = "()"
Output
1

Example 2

Input
s = "(())"
Output
2

Example 3

Input
s = "()()"
Output
2

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Stack approach: push 0 on every '('. On ')', pop the top v and replace it with max(2*v, 1) — added to whatever's now on top.

Hint 2

Start with a 0 on the stack representing the running sum at depth 0. Final answer is the value left on the stack.

Hint 3

Clever counting variant: every '()' core contributes 2^depth where depth is the number of unmatched '(' before it. Walk once, track depth, add 2^(depth-1) at each ')' that immediately follows a '('.

Hint 4

Both are O(n) — the counting variant uses O(1) extra space.

Solution approach

Reveal approach

Stack of partial scores. Push 0 at the start (the running score at the current depth). For each char c: if '(', push 0 (entering a new nesting level). If ')', pop the top v. If v == 0, this was an empty '()' core — add 1 to the new top. Otherwise add 2*v to the new top (the (A) rule). After scanning, the sum at the bottom of the stack is the answer. O(n) time, O(n) space. Alternative O(1)-space counting solution: track depth; for each ')' preceded by '(' (i.e., a core), add 2^(depth) to the answer. Each unique '()' core contributes 2^(its depth) by the doubling rule.

Complexity

Time
O(n)
Space
O(n) or O(1) with counting

Related patterns

  • stack
  • string
  • matching-bracket-stack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta

More Stacks practice problems

See all Stacks problems →