856. Score of Parentheses

MediumView on LeetCode

String Stack Math

Time: O(n)

Space: O(1)

Problem Overview

Use a stack to track running scores.

Intuition

Use a stack to track running scores. '(' pushes 0 (new context). ')' pops: if top was 0, contribute 1; else double the popped value. Add to new top.

Algorithm

1Initialize stack with [0].
2For '(': push 0.
3For ')': v = pop(). top += v == 0 ? 1 : 2*v.
4Return stack[0].

Example Walkthrough

Input: "(()(()))"

1.Push(0)(0)?pop 0?top+=1?[0,1]. Push(0)?pop 0?top+=1?[0,2]. Pop 2?top+=4?[4].

Output: 6

Common Pitfalls

•Empty pairs "()" score 1. Non-empty "(X)" score 2*score(X). The stack approach handles arbitrary nesting.

856.cs

// Approach: Single pass tracking nesting depth; each "()" contributes 1 << depth to the final score.
// Time: O(n) Space: O(1)

public class Solution
{
    public int ScoreOfParentheses(string s)
    {
        int ans = 0, layer = 0;
        for (int i = 0; i + 1 < s.Length; i++)
        {
            char a = s[i];
            char b = s[i + 1];

            if (a == '(' && b == ')')
                ans += (1 << layer);
            layer += (a == '(') ? 1 : -1;
        }

        return ans;
    }
}

Was this solution helpful?