## February LeetCoding Challenge 2021

Day 24

## score of parentheses

**PROBLEM STATEMENT:**

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.

**Example 1**

Input:"()"Output:1

**Example 2**

Input:"(())"Output:2

**Example 3**

Input:"()()"Output:2

**Example 4**

Input:"(()(()))"Output:6

**Note:**

`S`

is a balanced parentheses string, containing only`(`

and`)`

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

## Explanation

```
S = "((()(())))"
= "((1 + (1)))"
= 2^2 + 2^3
= 12
```

**ALGORITHM: **

- Traverse string from left to right.
- Keep track of number of ‘(‘ encountered as current power.
- If you reach a ‘)’ check if it has a ‘(‘ left of it.
- If yes, reduce the current power by 1 and add
`2`

to result.^{curr_power} - Else reduce the current power by 1 and continue.

- Time complexity : O(n)
- Space complexity : O(1)

## code

## C++

```
class Solution {
public:
int two_power(int n){
return 1 << n;
}
int scoreOfParentheses(string S) {
int res = 0;
int curr_power = 0;
for(int i=0;i<S.length();++i){
if(S[i] == '(') curr_power++;
else if(S[i-1] == '(') res += two_power(--curr_power);
else --curr_power;
}
return res;
}
};
```

## PYTHON

```
class Solution:
def two_power(self, n: int) -> int:
return 1 << n
def scoreOfParentheses(self, S: str) -> int:
res = 0
curr_power = 0
for i in range(len(S)):
if(S[i] == '('):
curr_power+=1
elif(S[i-1] == '('):
curr_power -= 1
res += self.two_power(curr_power)
else:
curr_power -= 1
return res
```