# Score of Parentheses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/score-of-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/score-of-parentheses
**Data structures:** String, Stack
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [Mountblue](https://scaleengineer.com/companies/mountblue)
---
## Problem
Given a balanced parentheses string `s`, return _the **score** of the string_.

The **score** of a balanced parentheses string is based on the following rule:

* `"()"` has score `1`.
* `AB` has score `A + B`, where `A` and `B` are balanced parentheses strings.
* `(A)` has score `2 * A`, where `A` is a balanced parentheses string.

**Example 1:**

**Input:** s = "()"
**Output:** 1

**Example 2:**

**Input:** s = "(())"
**Output:** 2

**Example 3:**

**Input:** s = "()()"
**Output:** 2

**Constraints:**

* `2 <= s.length <= 50`
* `s` consists of only `'('` and `')'`.
* `s` is a balanced parentheses string.

# Approaches
## Recursion (Divide and Conquer)
This approach directly translates the recursive definition of the score into a recursive function. A function `score(S)` will compute the score of a given balanced parentheses string `S`. The function determines if `S` is of the form `(A)` or `A+B` and calls itself recursively.
**Time:** O(N^2) to O(N^3). The complexity depends on the structure of the string and the implementation of `substring`. For a string like `((...))`, the recursion is `T(N) = T(N-2) + O(N)`, which solves to `O(N^2)`. If `substring` takes O(N), the complexity can reach O(N^3). · **Space:** O(N^2), where N is the length of the string. The recursion depth can go up to O(N), and each call might create substrings, leading to a total space usage of O(N^2).
**Pros:** Intuitive and directly follows the problem definition.; Relatively easy to understand and implement.
**Cons:** Inefficient due to repeated computations and string manipulations.; Higher time and space complexity compared to other methods.
### Explanation
The core idea is to implement a function that computes the score of a given string `s`. To distinguish between the `A+B` case and the `(A)` case, we can scan the substring and maintain a balance counter (increment for `(`, decrement for `)`). If the balance becomes zero at an index `k` before the end of the substring, it means the string is composed of two or more adjacent balanced strings. The first one is `s.substring(0, k+1)` and the rest is `s.substring(k+1)`. The score is then the sum of the scores of these two parts, computed recursively. If the balance never becomes zero until the very end, the string must be of the form `(A)`, where `A` is the inner substring. The score is `2 * score(A)`. The base case for the recursion is when the substring is `"()"`, which has a score of 1.

```java
class Solution {
    public int scoreOfParentheses(String s) {
        return score(s);
    }

    private int score(String s) {
        if (s.equals("()")) {
            return 1;
        }

        int balance = 0;
        int splitPoint = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance == 0 && i < s.length() - 1) {
                splitPoint = i;
                break;
            }
        }

        if (splitPoint != -1) {
            // Case AB: score(A) + score(B)
            String a = s.substring(0, splitPoint + 1);
            String b = s.substring(splitPoint + 1);
            return score(a) + score(b);
        } else {
            // Case (A): 2 * score(A)
            String a = s.substring(1, s.length() - 1);
            return 2 * score(a);
        }
    }
}
```
### Algorithm
- Define a recursive function `score(s)` that takes a string `s`.
- If `s` is `"()"` return 1.
- Initialize a balance counter `bal = 0`.
- Iterate through `s` from left to right (except the last character) to find a split point.
- Update `bal` for each character. If `bal` becomes 0 at index `i`, it means we found a split point. The string is `A+B` where `A = s.substring(0, i+1)` and `B = s.substring(i+1)`. Return `score(A) + score(B)`.
- If the loop completes without `bal` becoming 0, the string is of the form `(A)`. `A` is the inner part of `s`. Return `2 * score(s.substring(1, s.length()-1))`.

## Stack-based Calculation
This approach processes the string linearly and uses a stack to manage the scores of nested parentheses structures. The stack holds the scores of parenthetical groups at the current level of nesting.
**Time:** O(N), where N is the length of the string. We iterate through the string once, and each character involves a constant number of stack operations. · **Space:** O(N) in the worst case. The size of the stack is determined by the maximum depth of nested parentheses, which can be up to `N/2` for a string like `((...))`.
**Pros:** Much more efficient than the recursive approach.; Linear time complexity is optimal for reading the input.
**Cons:** Requires extra space for the stack, which can be proportional to the input size.
### Explanation
We can think of the problem as evaluating an expression. An opening parenthesis `(` starts a new "scope" or level of calculation, and a closing parenthesis `)` concludes the current scope's calculation and merges its result with the parent scope. We use a stack to keep track of the scores of previous, unfinished scopes. We also maintain a `currentScore` for the current level. When we encounter an `(`, we are entering a deeper level of nesting. We push the `currentScore` of the outer level onto the stack and reset `currentScore` to 0 for the new inner level. When we encounter a `)`, it signifies the end of the current level. The value of the just-closed group is either `1` (for an empty `()`) or `2 * currentScore` (for a non-empty `(A)`). This value is then added to the score of the parent level, which we retrieve by popping from the stack.

```java
import java.util.Stack;

class Solution {
    public int scoreOfParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        int currentScore = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(currentScore);
                currentScore = 0;
            } else {
                int lastScore = stack.pop();
                currentScore = lastScore + Math.max(2 * currentScore, 1);
            }
        }
        return currentScore;
    }
}
```
### Algorithm
- Initialize a stack of integers and a variable `currentScore = 0`.
- Iterate through each character `c` of the string `s`.
- If `c` is `(`, push the `currentScore` onto the stack and reset `currentScore` to 0.
- If `c` is `)`, pop the score of the enclosing scope from the stack. Let this be `lastScore`. The score of the just-closed group is `max(2 * currentScore, 1)`. Update `currentScore` to be `lastScore + max(2 * currentScore, 1)`.
- After the loop, `currentScore` will hold the final total score.

## Constant Space Calculation by Depth
This is the most optimal approach, achieving linear time with constant extra space. It works by observing that the total score is the sum of scores of all the primitive `()` pairs, where the score of each pair depends on its depth inside the string.
**Time:** O(N), as we perform a single pass through the string. · **Space:** O(1), as we only use a few variables to store the score and depth, regardless of the input string size.
**Pros:** Optimal time and space complexity.; Very efficient and concise.
**Cons:** The logic is less intuitive than the stack-based or recursive approaches and relies on a mathematical insight into the problem structure.
### Explanation
The final score can be seen as a sum of powers of 2. Each `()` pair in the string contributes to the total score. A `()` pair at a nesting depth `d` (i.e., enclosed by `d` pairs of parentheses) contributes `2^d` to the final score. For example, in `(()(()))`, the first `()` is at depth 1, contributing `2^1 = 2`. The second `()` is at depth 2, contributing `2^2 = 4`. The total score is `2 + 4 = 6`. We can iterate through the string, keeping track of the current depth. When we encounter a `()` pair (i.e., `s[i] == ')'` and `s[i-1] == '('`), we add `2^depth` to our total score. The depth here is the number of unmatched `(` parentheses enclosing the current `()` pair.

```java
class Solution {
    public int scoreOfParentheses(String s) {
        int score = 0;
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                depth++;
            } else {
                depth--;
                if (s.charAt(i - 1) == '(') {
                    score += 1 << depth; // 2^depth
                }
            }
        }
        return score;
    }
}
```
### Algorithm
- Initialize `score = 0` and `depth = 0`.
- Iterate through the string `s` from `i = 0` to `s.length() - 1`.
- If `s[i]` is `(`, increment `depth`.
- If `s[i]` is `)`, decrement `depth`.
- If `s[i]` is `)` and the previous character `s[i-1]` was `(`, this forms a core `()` unit. Add `1 << depth` (which is `2^depth`) to the `score`.
- After iterating through the entire string, `score` will hold the final result.

# Solutions
### Java

```java
class Solution { public int scoreOfParentheses ( String s ) { int ans = 0 , d = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { if ( s . charAt ( i ) == '(' ) { ++ d ; } else { -- d ; if ( s . charAt ( i - 1 ) == '(' ) { ans += 1 << d ; } } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int scoreOfParentheses ( string s ) { int ans = 0 , d = 0 ; for ( int i = 0 ; i < s . size (); ++ i ) { if ( s [ i ] == '(' ) { ++ d ; } else { -- d ; if ( s [ i - 1 ] == '(' ) { ans += 1 << d ; } } } return ans ; } };
```

### Python

```python
class Solution : def scoreOfParentheses ( self , s : str ) -> int : ans = d = 0 for i , c in enumerate ( s ): if c == '(' : d += 1 else : d -= 1 if s [ i - 1 ] == '(' : ans += 1 << d return ans
```