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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Score of Parentheses and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →