856. Score of Parentheses

Problem Description

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is 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:

Input: s = "()"
Output: 1

Input: s = "(())"
Output: 2

Input: s = "(()(()))"
Output: 6

Constraints:

• 2 ≤ s.length ≤ 50
• s consists of only '(' and ')'
• s is a balanced parentheses string

Python Solution

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]  # Stack to keep track of scores at each depth
        
        for char in s:
            if char == '(':
                stack.append(0)  # New depth level
            else:
                curr = stack.pop()  # Score at current depth
                stack[-1] += max(2 * curr, 1)  # Add to previous depth
        
        return stack[0]

Implementation Notes:

• Uses stack to track scores at different depths
• Time complexity: O(n)
• Space complexity: O(n)

Java Solution

class Solution {
    public int scoreOfParentheses(String s) {
        Stack stack = new Stack<>();
        stack.push(0);  // Initial score
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(0);  // New depth level
            } else {
                int curr = stack.pop();  // Score at current depth
                int prev = stack.pop();  // Score at previous depth
                stack.push(prev + Math.max(2 * curr, 1));
            }
        }
        
        return stack.pop();
    }
}

C++ Solution

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack st;
        st.push(0);  // Initial score
        
        for (char c : s) {
            if (c == '(') {
                st.push(0);  // New depth level
            } else {
                int curr = st.top();  // Score at current depth
                st.pop();
                int prev = st.top();  // Score at previous depth
                st.pop();
                st.push(prev + max(2 * curr, 1));
            }
        }
        
        return st.top();
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    const stack = [0];  // Stack to keep track of scores at each depth
    
    for (const char of s) {
        if (char === '(') {
            stack.push(0);  // New depth level
        } else {
            const curr = stack.pop();  // Score at current depth
            stack[stack.length - 1] += Math.max(2 * curr, 1);
        }
    }
    
    return stack[0];
};

C# Solution

public class Solution {
    public int ScoreOfParentheses(string s) {
        Stack stack = new Stack();
        stack.Push(0);  // Initial score
        
        foreach (char c in s) {
            if (c == '(') {
                stack.Push(0);  // New depth level
            } else {
                int curr = stack.Pop();  // Score at current depth
                int prev = stack.Pop();  // Score at previous depth
                stack.Push(prev + Math.Max(2 * curr, 1));
            }
        }
        
        return stack.Pop();
    }
}

Implementation Notes:

• Uses stack-based approach for nested parentheses
• Time complexity: O(n)
• Space complexity: O(n)