# LeetCode 856: Score of Parentheses

## Problem Restatement

We are given a balanced parentheses string `s`.

The score is defined by three rules:

| Form | Score |
|---|---|
| `"()"` | `1` |
| `AB` | `score(A) + score(B)` |
| `(A)` | `2 * score(A)` |

Here, `A` and `B` are balanced parentheses strings.

We need to return the score of `s`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A balanced parentheses string `s` |
| Output | The integer score of `s` |
| Constraint | `2 <= s.length <= 50` |
| Constraint | `s` contains only `'('` and `')'` |
| Guarantee | `s` is balanced |

Function shape:

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

## Examples

Example 1:

```python
s = "()"
```

The string is the base case.

```python
score("()") = 1
```

So the answer is:

```python
1
```

Example 2:

```python
s = "(())"
```

The inner string is:

```python
()
```

which has score `1`.

The outer parentheses double it:

```python
2 * 1 = 2
```

So the answer is:

```python
2
```

Example 3:

```python
s = "()()"
```

This is two balanced strings side by side:

```python
"()" + "()"
```

Each has score `1`, so the total is:

```python
1 + 1 = 2
```

Example 4:

```python
s = "(()(()))"
```

Inside the outer pair, we have:

```python
"()" + "(())"
```

Their scores are:

```python
1 + 2 = 3
```

The outer pair doubles the result:

```python
2 * 3 = 6
```

So the answer is:

```python
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:

```python
s = "(())"
```

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

```python
2
```

For:

```python
s = "((()))"
```

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

```python
4
```

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

```python
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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the string once |
| Space | `O(1)` | We only store `score` and `depth` |

## Implementation

```python
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:

```python
score = 0
depth = 0
```

`score` stores the answer.

`depth` stores how many open parentheses are currently active.

When we see an opening parenthesis:

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

we move one level deeper.

When we see a closing parenthesis:

```python
else:
    depth -= 1
```

we close one level.

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

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

The expression:

```python
1 << depth
```

means `2^depth`.

For example:

| `depth` | `1 << depth` |
|---|---|
| `0` | `1` |
| `1` | `2` |
| `2` | `4` |
| `3` | `8` |

Finally:

```python
return score
```

returns the total score.

## Testing

```python
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:

| Test | Why |
|---|---|
| `"()"` | Base score |
| `"(())"` | One nested pair |
| `"()()"` | Concatenation |
| `"(()(()))"` | Nested and concatenated groups |
| `"((()))"` | Multiple layers around one primitive pair |
| `"((())())"` | Mixed nesting inside one outer pair |