DDSA Solutions

856. Score of Parentheses

MediumView on LeetCode
StringStackMath
Time: O(n)
Space: O(1)

Problem Overview

Only an empty pair () creates score.

Intuition

Only an empty pair () creates score. Every pair wrapped around it doubles that value, and side by side pieces simply add. So an empty pair nested inside d other pairs contributes 2 to the power d, and the total is the sum over all empty pairs. Tracking the current depth while scanning finds each empty pair and its depth in one pass, with no stack.

Algorithm

  1. 1Start the answer and the depth at 0.
  2. 2Look at each character together with the next one.
  3. 3If an opening parenthesis is immediately followed by a closing one, add 1 shifted left by the current depth.
  4. 4Increase the depth on an opening parenthesis and decrease it on a closing one.
  5. 5Return the answer.

Example Walkthrough

Input: s = "(()(()))"

  1. 1.The first empty pair starts at index 1, inside one outer pair, so it adds 2.
  2. 2.The second empty pair starts at index 4, inside two pairs, so it adds 4.
  3. 3.No other opener is followed directly by a closer, so the total is 6.

Output: 6

Common Pitfalls

  • •Only an opener directly followed by a closer scores. A closer that ends a bigger group adds nothing by itself.
  • •Read the depth before updating it for the current opener, so the empty pair uses the depth of the pairs around it.
  • •The constraints keep the depth small, so the shifted value fits in an int.
  • •A stack of partial scores gives the same answer but uses linear memory. The depth counter needs constant memory.
856.cs
C#
// 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?

Related Problems