*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #856 (*Medium*): Score of Parentheses

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:*

*Examples:*

Example 1: Input: "()" Output: 1

Example 2: Input: "(())" Output: 2

Example 3: Input: "()()" Output: 2

Example 4: Input: "(()(()))" Output: 6

####
*Constraints:*

*Constraints:*

`S`

is a balanced parentheses string, containing only`(`

and`)`

.`2 <= S.length <= 50`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:

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

*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:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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;
}
};
```

## Discussion (0)