Score of Parentheses

medium string stack

Problem

Given a balanced parentheses string, compute its score: () = 1, AB = A + B, (A) = 2 · A.

Inputs = "(()(()))"

Output6

Two "()" atoms at depths 2 and 3 contribute 2 + 4 = 6.

def scoreOfParentheses(s):
    depth = 0
    score = 0
    for i, c in enumerate(s):
        if c == '(':
            depth += 1
        else:
            depth -= 1
            if s[i - 1] == '(':
                score += 1 << depth
    return score

function scoreOfParentheses(s) {
  let depth = 0, score = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') depth++;
    else {
      depth--;
      if (s[i - 1] === '(') score += 1 << depth;
    }
  }
  return score;
}

class Solution {
    public int scoreOfParentheses(String s) {
        int depth = 0, score = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') depth++;
            else {
                depth--;
                if (s.charAt(i - 1) == '(') score += 1 << depth;
            }
        }
        return score;
    }
}

int scoreOfParentheses(string s) {
    int depth = 0, score = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') depth++;
        else {
            depth--;
            if (s[i - 1] == '(') score += 1 << depth;
        }
    }
    return score;
}

Explanation

The scoring rules (() = 1, nesting doubles, side-by-side adds) sound recursive, but there is a neat shortcut: the only thing that actually scores is each innermost () atom. Everything else is just doubling from the layers wrapped around it.

An atom nested at depth d contributes 2^(d-1), because every enclosing pair doubles it. So we walk the string tracking the current depth, and whenever we see a ) that immediately follows a ( — that is the pattern () — we add its value to the running score.

In code, ( increases depth and ) decreases it. When we close a pair, we check s[i-1] == '(' to detect an atom, and add 1 << depth (which is 2^depth) using the depth after the decrement.

Example: s = "(()(()))". There are two () atoms. One sits at depth 2 and adds 2; the other sits at depth 3 and adds 4. Total = 6.

Since we only track an integer depth and a score, this needs no stack and just one pass over the string.

Time: O(n) Space: O(1)