Score of Parentheses

Medium
378.

Score of Parentheses

Score of Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google and Meta interviews.

Given a balanced parentheses string s, compute its score under these rules:

  • "()" scores 1;
  • AB scores A + B, where A and B are balanced strings;
  • (A) scores 2 * A.

Example 1

Input
s = "()"
Output
1

Example 2

Input
s = "(())"
Output
2

Example 3

Input
s = "()()"
Output
2

Constraints

  • 2 <= s.length <= 30
  • s is a balanced parentheses string.
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Score of Parentheses — Solution in Python, Java & C++

Score of Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Score of Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Strings, Stack
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a balanced parentheses string s, compute its score under these rules:

  • "()" scores 1;
  • AB scores A + B, where A and B are balanced strings;
  • (A) scores 2 * A.

Example 1

Input: s = "()"
Output: 1

Example 2

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

Example 3

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

Constraints

  • 2 <= s.length <= 30
  • s is a balanced parentheses string.
  • The answer fits in a signed 32-bit integer.

Hints for Score of Parentheses

  1. Hint 1

    Keep a stack of partial scores, one frame per open bracket, plus one frame for the whole string.

  2. Hint 2

    On (, push a new frame holding 0.

  3. Hint 3

    On ), pop the frame: a score of 0 means it was a bare () worth 1, otherwise it is worth double. Add that into the frame below.

How to solve Score of Parentheses

Keep a stack of partial scores, one frame per open bracket; on ), pop the frame and add 1 (if it was empty) or 2 · inner to the frame below.

Approach

  1. Start stack = [0].
  2. On (, push 0; on ), pop inner and add 1 if inner == 0 else 2 · inner to the new top.
  3. Return stack[0].

Why it works

Each frame accumulates the A + B sum of its siblings; closing a frame applies the (A) doubling rule, with the base case () scoring 1.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The O(1)-space trick counts each () as 2^depth where depth is the number of enclosing brackets.

Reference solution

Python

def scoreOfParentheses(s: str) -> int:
    stack = [0]
    for ch in s:
        if ch == "(":
            stack.append(0)
        else:
            inner = stack.pop()
            stack[-1] += 1 if inner == 0 else 2 * inner
    return stack[0]

Java

public static int scoreOfParentheses(String s) {
    List<Integer> stack = new ArrayList<>();
    stack.add(0);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.add(0);
        } else {
            int inner = stack.remove(stack.size() - 1);
            int value = inner == 0 ? 1 : 2 * inner;
            stack.set(stack.size() - 1, stack.get(stack.size() - 1) + value);
        }
    }
    return stack.get(0);
}

C++

int scoreOfParentheses(string s) {
    vector<int> stack;
    stack.push_back(0);
    for (char c : s) {
        if (c == '(') {
            stack.push_back(0);
        } else {
            int inner = stack.back();
            stack.pop_back();
            stack.back() += (inner == 0 ? 1 : 2 * inner);
        }
    }
    return stack[0];
}

JavaScript

var scoreOfParentheses = function(s) {
    const stack = [0];
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === "(") {
            stack.push(0);
        } else {
            const inner = stack.pop();
            const value = inner === 0 ? 1 : 2 * inner;
            stack[stack.length - 1] += value;
        }
    }
    return stack[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure