Solution Explanation: Score of Parentheses

The problem asks to calculate the score of a balanced parentheses string based on specific rules. The rules leverage recursion and the structure of nested parentheses. Instead of a recursive approach, a more efficient iterative solution using a stack is possible but not necessary given the problem constraints. This solution utilizes a clever observation to directly calculate the score in linear time.

Core Idea:

The key observation is that the score is determined solely by the innermost () pairs and their nesting levels. Each innermost () pair contributes a score of 1. The contribution of each () pair is then multiplied by 2 for each level of nesting it is within.

Algorithm:

1. Initialization: We initialize ans (the total score) to 0 and d (the depth of nested parentheses) to 0.

2. Iteration: We iterate through the input string s.

   • If we encounter an opening parenthesis (, we increment the depth d.
   • If we encounter a closing parenthesis ), we decrement the depth d. Crucially, if the preceding character was an opening parenthesis (, it indicates an innermost () pair at the current depth. The score contribution of this pair is 2d (because d is decremented immediately afterward). We add this score to ans.

3. Return: After iterating through the entire string, ans contains the total score, which is returned.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
• Space Complexity: O(1). We use only a few integer variables; the space used is constant regardless of the input size.

Code Examples:

Python:

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = d = 0
        for i, c in enumerate(s):
            if c == '(':
                d += 1
            else:
                d -= 1
                if s[i - 1] == '(':
                    ans += 1 << d
        return ans

Java:

class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                d++;
            } else {
                d--;
                if (s.charAt(i - 1) == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int scoreOfParentheses(string s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                d++;
            } else {
                d--;
                if (s[i - 1] == '(') {
                    ans += (1 << d); // More efficient bit shift
                }
            }
        }
        return ans;
    }
};

Go:

func scoreOfParentheses(s string) int {
	ans, d := 0, 0
	for i, c := range s {
		if c == '(' {
			d++
		} else {
			d--
			if s[i-1] == '(' {
				ans += 1 << d
			}
		}
	}
	return ans
}

All the code examples follow the same algorithm, demonstrating its simplicity and efficiency. The use of bit shifting (1 << d) is a concise way to calculate 2d.