DSA sheet · Stack · Pattern 4: parentheses & scoring

Score of Parentheses

The third question of the parentheses pattern, and the first one about scoring. The teacher warns that it feels hard the first time but is unforgettable once it clicks. She solves it twice: first with a stack of scores, where the strange-looking trick is to push a 0 before starting and a 0 for every opener; then with no stack at all, using only the current depth and a bit shift (1 << depth). Both are O(n) time; the second is O(1) space.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch + the parentheses pattern
• Part A · Stack of scores
• Part B · Space optimised: depth counter + shift
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A pile where you can only add to the top and remove from the top: LIFO, Last In First Out.

Drawings: stack written left = bottom, right = top. Vertical pictures: top in red.

The parentheses pattern, scoring flavour

In Valid Parentheses the stack held the openers still waiting. A closer always finished the most recent opener. Here the same is true, but instead of the opener character we keep a number for each open level: "the score collected so far inside this bracket". When the bracket closes, we turn that number into the bracket's score and hand it to the level outside. The stack lets us look back to the outer levels, and the teacher's rule is: whenever you need to look back, think stack (it turns an O(n²) look-back into O(n)).

The counter trick

Only ( and ) appear, one family. So in Part B we replace the stack with a single integer depth (how many brackets are open right now), which gives O(1) space.

Bit shift in one line

1 << k means "write 1 in binary and add k zeros on the right", which is 2^k. 1<<0 = 1, 1<<1 = 2 (binary 10), 1<<2 = 4 (binary 100), 1<<3 = 8.

Part A · Stack of scores

LeetCode 856

1The question in simple words

You get a balanced string of ( and ) (every opener has its closer in the right place, as in Valid Parentheses). Compute its score with three rules:

The teacher's examples:

• () → 1. ()() → 1 + 1 = 2.
• ((())): the innermost () is 1. One wrap → 2. Another wrap → 4. Each extra layer doubles: one more layer would give 8.
• ((())()):

  ( ( ( ) ) ( ) )
      └─┘          inner ()           = 1
    └─────┘        wrapped once       = 2 × 1 = 2
            └─┘    sibling ()         = 1      → siblings add: 2 + 1 = 3
  └─────────────┘  outer bracket      = 2 × 3 = 6

2What the constraints tell us

• 2 ≤ s.length ≤ 50, only ( and ), and s is balanced → no validity checks needed; the stack never runs dry.
• n is tiny, so any approach is fast enough. The point of this problem is the clean O(n) idea and then the O(1)-space idea, which is what interviewers want to see.
• The deepest nesting is 25 levels, so the score fits easily in an int (2²⁴).

3Intuition: what does a closer need to know?

When we hit a ), we must decide this bracket's score. Two numbers decide it:

1. The score of what's inside this bracket (call it v). If nothing is inside, v = 0 and the bracket is worth 1. Otherwise it's worth 2 × v. In one formula: max(2 * v, 1).
2. The score already collected just before this bracket opened, at the same level (its earlier siblings). Siblings add, so our bracket's score must be added to that.

So the stack keeps, for every currently open level, "the score collected so far at that level". The top is the level inside the bracket we're closing (that's v, to be multiplied); the one below it is the level outside (to be added to).

4Building the logic from examples

Why push 0 for every opener?

Opening a bracket starts a new level where nothing has been scored yet. So push 0. The closer will later read that number.

Why push one extra 0 before we even start?

That bottom 0 stands for "the whole string's level", the score collected outside every bracket. When a top-level bracket like the first () in ()(()) closes, its score has to be added somewhere. The extra 0 is that place. At the end it holds the total, which is the answer.

Example ()(()): the stack design

When we reach the first ) of (()) (index 4), the stack is [1, 0, 0]: bottom 1 = the earlier sibling (), then 0 for the outer bracket, then 0 for the inner bracket. The inner pair becomes max(2×0, 1) = 1 and is added to the level below → [1, 1]. At index 5 the outer bracket closes: v = 1 → 2 × 1 = 2, added to the bottom → [3]. Answer 3 = 1 + 2 ✓. The teacher's summary: the top gets multiplied, the one under it gets added to.

The catch: 2 × 0 = 0, so use max

For the simplest (), v = 0, and 2 × 0 = 0. But () must score 1. So the bracket's score is max(2 * v, 1): if anything was inside, double it; if nothing was inside, it's 1.

The two pops

On a closer the teacher pops twice: once to get v (the inside score), and once to get the outer level's score, then pushes back "outer + this bracket". In Python it's simpler to pop once and add straight into the new top: stack[-1] += score. Same effect: pop v, pop outer, push outer + score.

5Approach steps

1. stack = [0]: the score of the outermost level.
2. For each character: ( → push 0 (a new level starts).
3. ) → v = stack.pop() (inside score); score = max(2 * v, 1); add it to the level outside: stack[-1] += score.
4. At the end, the only item left is the total → return stack[-1] (or pop it).

6Code (Python)

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]                     # score of the outermost level
        for ch in s:
            if ch == '(':
                stack.append(0)         # a new level, nothing scored inside yet
            else:
                v = stack.pop()         # what this bracket contains
                score = max(2 * v, 1)   # () = 1, (A) = 2*A
                stack[-1] += score      # siblings add: give it to the outer level
        return stack.pop()

7Code line by line

8Dry run: the teacher's "messy" example ((()()))()

  ( ( ( ) ( ) ) ) ( )
  0 1 2 3 4 5 6 7 8 9      index
      └─┘ └─┘              two inner ()        = 1 + 1 = 2
    └─────────┘            wrapped once        = 4
  └─────────────┘          wrapped again       = 8
                  └─┘      sibling ()          = 1     → total 9

Look at i = 8: the extra 0 pushed for the last ( keeps that new bracket's score separate from the 8, so the 8 is added to (8 + 1), not doubled. That's exactly why we push a 0 per opener and keep a floor below.

9Complexity & remember

• Time O(n): one loop, O(1) work per character.
• Space O(n): one stack entry per open level. The teacher notes that at most about n/2 openers can be open at once (the other half are closers), and n/2 is still linear.

Part B · Space optimised: depth counter + shift

1The question (same)

Same balanced string, same scoring rules. Now with O(1) extra space.

2Constraints

One bracket family and a balanced string → the counter trick applies. Depth ≤ 25, so 1 << depth is a small number.

3Intuition: only the empty pairs score, and their depth decides how much

The stack solution works inside → out: score the inner pair, then double it on the way out. The teacher flips it to outside → in: when we meet an empty pair (), we already know how many brackets wrap it (the current depth). Each wrap doubles it, so this () contributes

1 << (number of brackets around it) = 2^depth

And the total score is just the sum over all empty pairs. Why? Doubling spreads over a sum: 2 × (A + B) = 2A + 2B. So instead of adding the insides and then doubling, we can double each () separately by its own depth and add everything at the end.

Check with ((())): one empty pair, wrapped by 2 brackets → 1 << 2 = 4 (binary 100) ✓. And ((()()))(): two pairs at depth 2 → 4 + 4, one pair at depth 0 → 1. Total 9 ✓.

4Building the logic from examples

Keep a depth count

( → depth += 1. ) → depth -= 1. After decreasing at a closer, depth equals the number of brackets around the pair that just closed. That's the shift amount.

Which closers score? Only the ones right after an opener

In ((()()))(), the closer at index 6 closes a bracket that has stuff inside. Its value was already counted when we scored the inner ()s at their depth (their 1s already include the doubling from this bracket). Counting it again would double count. So: score only when s[i-1] == '(', which means "this closer finishes an empty pair". Every other closer just decreases the depth.

5Approach steps

1. depth = 0, score = 0.
2. For each index i: if s[i] == '(' → depth += 1.
3. Else → depth -= 1; if s[i-1] == '(' → score += 1 << depth.
4. Return score.

6Code (Python)

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        depth = 0                       # brackets open right now
        score = 0
        for i in range(len(s)):
            if s[i] == '(':
                depth += 1
            else:
                depth -= 1              # now = brackets AROUND this pair
                if s[i - 1] == '(':     # an empty pair "()" just closed
                    score += 1 << depth # 2 ** depth
        return score

7Code line by line

8Dry run: ((()()))()

Same answer as the stack (9), with just two integers.

9Complexity & remember

• Time O(n), space O(1): only depth and score.

Part C · Revision page

s = Solution()
print(s.scoreOfParentheses("()"))          # 1
print(s.scoreOfParentheses("()()"))        # 2
print(s.scoreOfParentheses("(())"))        # 2
print(s.scoreOfParentheses("((()))"))      # 4
print(s.scoreOfParentheses("()(())"))      # 3
print(s.scoreOfParentheses("((())())"))    # 6
print(s.scoreOfParentheses("((()()))()"))  # 9

Based on this video: Score of Parentheses | Stack pattern: parentheses & scoring