Code Implementation

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]
        for char in s:
            if char == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)
        return stack[0]
      

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        st.push(0);
        for (char c : s) {
            if (c == '(') {
                st.push(0);
            } else {
                int v = st.top(); st.pop();
                int w = st.top(); st.pop();
                st.push(w + max(2 * v, 1));
            }
        }
        return st.top();
    }
};
      

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(0);
            } else {
                int v = stack.pop();
                int w = stack.pop();
                stack.push(w + Math.max(2 * v, 1));
            }
        }
        return stack.peek();
    }
}
      

var scoreOfParentheses = function(s) {
    let stack = [0];
    for (let c of s) {
        if (c === '(') {
            stack.push(0);
        } else {
            let v = stack.pop();
            stack[stack.length - 1] += Math.max(2 * v, 1);
        }
    }
    return stack[0];
};
      

Problem Description

Given a balanced parentheses string s, compute its score based on the following rules:

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

You are given a string s consisting only of '(' and ')' characters, and s is guaranteed to be a valid balanced parentheses string. Your task is to return the score of s according to the rules above.

Constraints:

• 1 ≤ len(s) ≤ 50
• s is a balanced parentheses string

Thought Process

At first glance, this problem seems like it requires parsing and recursively evaluating the structure of the parentheses. If we try to brute-force, we might attempt to split the string at every level, recursively score the substrings, and combine the results. However, this would be inefficient and complex.

The key insight is to recognize that the score depends on the structure of the parentheses, not on their specific positions. The rules are recursive and compositional, so we can process the string in one pass, keeping track of the current "depth" or using a stack to manage nested expressions.

Instead of recursively splitting, we can use a stack to simulate the process, adding scores as we close parentheses, and doubling scores when we encounter nested pairs. This approach is both efficient and elegant.

Solution Approach

• Use a Stack: We use a stack to keep track of the score at each level of nesting. Each '(' pushes a new score context onto the stack.
• Processing ')': When we see a ')', we pop the top score. If the popped score is 0, it means we just closed a pair '()', so we add 1 to the previous context. If it's greater than 0, it means we closed a nested structure, so we double it and add to the previous context.
• Final Score: After processing the entire string, the answer is the score left at the bottom of the stack.

This approach works because the stack naturally mirrors the nested structure of the parentheses, and we always combine scores according to the problem's rules as we unwind the stack.

1. Initialize a stack with a single 0 (this will accumulate the total score).
2. For each character in the string:
   • If '(', push 0 onto the stack (start a new score context).
   • If ')', pop the top value v. If v == 0, add 1 to the new top of the stack. Otherwise, add 2 * v to the new top.
3. Return the value at the bottom of the stack.

Example Walkthrough

Let's walk through the input s = "(()(()))" step by step:

1. Start: stack = [0]
2. Read '(': stack = [0, 0]
3. Read '(': stack = [0, 0, 0]
4. Read ')': pop 0, since it's 0, add 1 to previous: stack = [0, 1]
5. Read '(': stack = [0, 1, 0]
6. Read '(': stack = [0, 1, 0, 0]
7. Read ')': pop 0, add 1 to previous: stack = [0, 1, 1]
8. Read ')': pop 1, add 2*1=2 to previous: stack = [0, 3]
9. Read ')': pop 3, add 2*3=6 to previous: stack = [6]

The final score is 6.

This shows how the stack accumulates scores as we close parentheses, handling both simple and nested cases.

Time and Space Complexity

• Brute-Force Approach: Recursively splitting and scoring substrings would take exponential time in the worst case, as each split could generate multiple recursive calls. Space usage would also be high due to recursion stack and substring copies.
• Optimized Stack Approach: Each character is processed exactly once, and each stack operation is O(1). Thus, the time complexity is O(N), where N is the length of the string. The space complexity is also O(N) in the worst case (for deeply nested strings), but typically much less.

Summary

The "Score of Parentheses" problem can be solved efficiently using a stack to track the score at each level of nesting. By simulating the process of evaluating the parentheses structure, we avoid the complexity of recursion and achieve a linear-time solution. The key insight is to interpret the problem's rules in terms of stack operations, making the solution both concise and elegant.