###### Score of Parentheses | February Leetcoding Challenge 2021 | Day 24
Manas Sinha
Developer | Designer

## 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``````
As you can see in the above Example after we replace () with 1, the number of parentheses encapsulating this () is how many times it needs to be multiplied by two. And we don’t need to wait to reach the end of the string as the multiplication operation will be distributed.
`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 `2curr_power` to result.
• Else reduce the current power by 1 and continue.
• Time complexity : O(n)
• Space complexity : O(1)

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