LeetCode 856: Score of Parentheses

Problem Restatement

We are given a balanced parentheses string s.

The score is defined by three rules:

Here, A and B are balanced parentheses strings.

We need to return the score of s.

Input and Output

Function shape:

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ...

Examples

Example 1:

s = "()"

The string is the base case.

score("()") = 1

So the answer is:

1

Example 2:

s = "(())"

The inner string is:

()

which has score 1.

The outer parentheses double it:

2 * 1 = 2

So the answer is:

2

Example 3:

s = "()()"

This is two balanced strings side by side:

"()" + "()"

Each has score 1, so the total is:

1 + 1 = 2

Example 4:

s = "(()(()))"

Inside the outer pair, we have:

"()" + "(())"

Their scores are:

1 + 2 = 3

The outer pair doubles the result:

2 * 3 = 6

So the answer is:

6

First Thought: Use a Stack

The scoring rules are recursive.

A natural way to model them is with a stack.

When we see '(', we start a new nested group.

When we see ')', we close the current group.

If the current group is empty, then it represents "()", with score 1.

If the current group already has a score, then wrapping it in parentheses doubles it.

This works, but there is an even simpler way.

Key Insight

Only the primitive pair "()" directly contributes score.

Outer parentheses only multiply that contribution by powers of two.

For example:

s = "(())"

The primitive pair "()" is inside one outer pair, so its contribution is:

2

For:

s = "((()))"

The primitive pair is inside two outer pairs, so its contribution is:

4

In general, when we see a primitive pair "()" at depth d, it contributes:

2^d

where d is the number of outer pairs around it.

So we scan the string, track the current depth, and add a value whenever we find "()".

Algorithm

Maintain two variables:

score = 0
depth = 0

Scan the string from left to right.

For each character:

1. If the character is '(', increase depth.
2. If the character is ')', decrease depth.
3. If the current character is ')' and the previous character is '(', then we found a primitive pair "()".
4. Add:

1 << depth

to the score.

The order matters.

When we see ')', we first decrease depth.

After decreasing, depth equals the number of outer pairs around this primitive "()".

Correctness

Every balanced parentheses string can be decomposed into primitive pairs "()", with some number of outer parentheses around each primitive pair.

The scoring rules imply that concatenation adds scores, while wrapping in parentheses doubles the score.

Therefore, each primitive pair contributes 1 multiplied by 2 once for every outer pair around it.

So a primitive pair at outer depth d contributes 2^d.

The algorithm finds exactly the primitive pairs by checking where a ')' is immediately preceded by '('.

For each such pair, after decrementing depth, the variable depth equals the number of outer pairs surrounding that primitive pair. The algorithm adds 2^depth, which is exactly that pair’s contribution.

Since every score contribution comes from one primitive pair, and every primitive pair is counted once, the final score is correct.

Complexity

Implementation

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        score = 0
        depth = 0

        for i, char in enumerate(s):
            if char == "(":
                depth += 1
            else:
                depth -= 1

                if s[i - 1] == "(":
                    score += 1 << depth

        return score

Code Explanation

We start with:

score = 0
depth = 0

score stores the answer.

depth stores how many open parentheses are currently active.

When we see an opening parenthesis:

if char == "(":
    depth += 1

we move one level deeper.

When we see a closing parenthesis:

else:
    depth -= 1

we close one level.

After closing, if the previous character was '(', then the current pair is a primitive "()":

if s[i - 1] == "(":
    score += 1 << depth

The expression:

1 << depth

means 2^depth.

For example:

Finally:

return score

returns the total score.

Testing

def test_score_of_parentheses():
    s = Solution()

    assert s.scoreOfParentheses("()") == 1
    assert s.scoreOfParentheses("(())") == 2
    assert s.scoreOfParentheses("()()") == 2
    assert s.scoreOfParentheses("(()(()))") == 6
    assert s.scoreOfParentheses("((()))") == 4
    assert s.scoreOfParentheses("((())())") == 6

    print("all tests passed")

test_score_of_parentheses()

Test meaning: