Solution: Score of Parentheses
Tags: algorithms, javascript, java, python
Published: 2021-02-24 10:22:06

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/discuss/topic/1080625).*

---

#### [Leetcode Problem #856 (*Medium*): Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given a balanced parentheses string `S`, compute the score of the string 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.

---

#### ***Examples:***

>
Example 1:||
|---:|---|
Input:|"()"
Output:|1
>
Example 2:||
|---:|---|
Input:|"(())"
Output:|2
>
Example 3:||
|---:|---|
Input:|"()()"
Output:|2
>
Example 4:||
|---:|---|
Input:|"(()(()))"
Output:|6

---

#### ***Constraints:***
>
 - `S` is a balanced parentheses string, containing only `(` and `)`.
 - `2 <= S.length <= 50`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Any time we see a problem that describes a doubling operation and an incrementing operation, we should at least think about a potential binary solution. In this case, those are really the only two operations. Nested doubling operations means powers of **2** depending on the nesting depth, and a simple closed pair of parentheses is a **+1**.

At first glance, the addition operation would seem to cause a problem, but math onces again comes to our aid.

Consider the following:
```js
S = "(((()()())))"
  = "(((" 1 + 1 + 1 ")))"    // After replacing completed "()"s with 1s
  = (1 + 1 + 1) * 2^3        // Applying the power operations
  = 2^3 + 2^3 + 2^3          // Through the distributive property of multiplication
```
As we can see, we don't *really* have to wait for the summation before applying the power operation, because it will get distributed across the summation anyway. And since we know how many nested parentheses there are (**pwr**) when we finish a simple parentheses pair, we can immediately add the appropriate value to our answer (**ans**).

This means that we can solve this problem in **O(n) time** and **O(1) space**.

---

#### ***Implementation:***

For JavaScript **S.charAt(i)** is faster at processing string iteration than **S[i]**.

We can start our iteration at **i = 1** because we know the first character is going to be **"("**. We *could* start at **i = 0**, but then we'd have to either start with **pwr = 1** or make sure to decrement **pwr** before the power operation instead of after.

We can use a **bitwise shift** for the power operation to more accurately reflect the solution's binary nature.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var scoreOfParentheses = function(S) {
    let len = S.length, pwr = 0, ans = 0
    for (let i = 1; i < len; i++)
        if (S.charAt(i) === "(") pwr++
        else if (S.charAt(i-1) === "(") ans += 1 << pwr--
        else pwr--  
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        pwr, ans = 0, 0
        for i in range(1, len(S)):
            if S[i] == "(": pwr += 1
            elif S[i-1] == "(":
                ans += 1 << pwr
                pwr -= 1
            else: pwr -= 1
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int scoreOfParentheses(String S) {
        int len = S.length(), pwr = 0, ans = 0;
        for (int i = 1; i < len; i++)
            if (S.charAt(i) == '(') pwr++;
            else if (S.charAt(i-1) == '(') ans += 1 << pwr--;
            else pwr--;
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int scoreOfParentheses(string S) {
        int len = S.length(), pwr = 0, ans = 0;
        for (int i = 1; i < len; i++)
            if (S[i] == '(') pwr++;
            else if (S[i-1] == '(') ans += 1 << pwr--;
            else pwr--;
        return ans;
    }
};
```