Solution: Score of Parentheses

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:

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

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:

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

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:

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

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

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

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