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

By Manas | 24 February 2021

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
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)

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

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply