Leetcode 856. Score of Parentheses

Problem

The problem requires us to compute the score of a string that contains a balanced parantheses. Balanced parantheses means that for every opening parantheses "(" there is a closing parantheses ")".

The scoring rules are as follows:

• "()" has a score of 1.
• "AB" has a score of A + B where A and B are balanced parantheses strings.
• "(A)" has a score of 2 * A where A is a balanced parantheses string.

We are guaranteed that the input string is always a balanced parantheses string and its length will always be between 2 and 50.

Approach

To solve this problem, we keep track of the "layer" of parantheses we are in. We increment the layer when we encounter an opening parantheses "(" and decrement when we encounter a closing parantheses ")". Now, when we encounter a pair of parantheses "()", we add score of 1 << layer to the final answer. We use bit shift here because multiplying score by 2 for each layer is equivalent to shifting the number to the left by that amount.

Examples

Let's walk through an example with input "(()(()))".

First we initialize ans = 0 and layer = 0.

Next, we iterate over the characters in the string. In the first iteration i=0, a='(' and b='('. We increment layer to 1 because a is an opening parantheses.

In the second iteration i=1, a='(' and b='('. We increment layer to 2.

In the third iteration i=2, a='(' and b=')'. We add 1 << layer = 1 << 2 = 4 to ans and decrement layer to 1.

We continue this process for the rest of the characters and finally return ans.

Python Solution

The Python solution would look something like this:

1
2python
3class Solution:
4    def scoreOfParentheses(self, S: str) -> int:
5        ans, layer = 0, 0
6        for i in range(len(S)-1):
7            if S[i] == "(":
8                if S[i+1] == ")":
9                    ans += 1 << layer
10                layer += 1
11            if S[i] == ")":
12                layer -= 1
13        return ans

Java Solution

Here is how we can implement the same idea in Java:

1
2java
3class Solution {
4    public int scoreOfParentheses(String S) {
5        int ans = 0;
6        int layer = 0;
7
8        for (int i = 0; i < S.length() - 1; ++i) {
9            if (S.charAt(i) == '(') {
10                if (S.charAt(i+1) == ')')
11                    ans += 1 << layer;
12                layer += 1;
13            }
14            if (S.charAt(i) == ')')
15                layer -= 1;
16        }
17
18        return ans;
19    }
20}

JavaScript Solution

The solution in JavaScript would be:

1
2javascript
3var scoreOfParentheses = function(S) {
4    let ans = 0, layer = 0;
5
6    for (let i = 0; i < S.length - 1; ++i) {
7        if (S[i] == '(') {
8            if (S[i + 1] == ')')
9                ans += 1 << layer;
10            layer += 1;
11        }
12        if (S[i] == ')')
13            layer -= 1;
14    }
15
16    return ans;
17};

C++ Solution

And finally, here is the C++ solution:

1
2c++
3class Solution {
4public:
5    int scoreOfParentheses(string S) {
6        int ans = 0, layer = 0;
7
8        for (int i = 0; i + 1 < S.size(); ++i) {
9            if (S[i] == '(') {
10                if (S[i+1] == ')')
11                    ans += 1 << layer;
12                layer += 1;
13            }
14            if (S[i] == ')')
15                layer -= 1;
16        }
17
18        return ans;
19    }
20};

C# Solution

In C#, the solution could look like this:

1
2csharp
3public class Solution {
4    public int ScoreOfParentheses(string S) {
5        int ans = 0, layer = 0;
6
7        for (int i = 0; i < S.Length - 1; ++i) {
8            if (S[i] == '(') {
9                if (S[i+1] == ')')
10                    ans += 1 << layer;
11                layer += 1;
12            }
13            if (S[i] == ')')
14                layer -= 1;
15        }
16
17        return ans;
18    }
19}

Comments in the solution explain how each of the steps in each iteration work. Overall, the complexity of the solution is linear regarding the size of the input which makes it quite effecient for this problem constraints.## Conclusions and Further Improvements

This solution uses bit shifting to determine the score of each valid pair of parentheses. Bit shifts may seem a bit obscure if you haven't used them before, but they're simply a way of multiplying or dividing a number by 2. In this case, it's used to double the score for each nested layer of parentheses.

As for time complexity, this solution has O(n) since we only need to iterate over the string once. The space complexity is also O(1) because the space required does not increase with the size of the input string.

This implementation is already pretty optimized, due to its low time and space complexity. In terms of possible improvements, it will largely depend on the specific circumstances and constraints. If the length of the string were to increase dramatically, we could consider ways to parallelize the computation.

However, given the constraints in this problem (i.e., the size of the input string is guaranteed to be between 2 and 50), this solution should be more than efficient to handle even the largest possible inputs.

As it often happens in programming, there's more than one way to solve a problem. Another approach could be using a stack to keep track of the score within each layer of parentheses, popping the score when we encounter a closing parenthesis and adding the double score (or one, if the score of the current layer is zero) to the score of the next layer. This could be a good solution if you struggle with bit-wise shift operation. However, this solution also has a O(n) time complexity, and a O(n) space complexity, because in the worst case all characters in the string will be pushed onto the stack.

Exploring different solutions and really understanding them is a great way to improve your skills as a programmer.