LeetCode 856 - Score of Parentheses

LeetCode Problem 856

Difficulty: 🟡 Medium
Topics: String, Stack

Solution

Problem Understanding

The problem is asking us to compute a score for a string of balanced parentheses according to a set of rules. A balanced parentheses string is one in which every opening parenthesis '(' has a corresponding closing parenthesis ')' and the pairs are properly nested. The rules for scoring are as follows:

1. A single pair "()" scores 1.
2. Concatenation of balanced strings AB scores A + B.
3. A string enclosed in parentheses (A) scores 2 * A.

In other words, the score of a string is recursively defined: atomic "()" contributes 1, nesting multiplies by 2, and sequential structures sum up. The input s is guaranteed to be balanced and consists solely of '(' and ')'. The constraints are small (2 <= s.length <= 50), which allows solutions with linear or near-linear complexity, but inefficient approaches like fully recursive parsing with substring slicing could still be slower due to repeated string operations.

Important edge cases to consider include strings with only a single pair "()", fully nested structures like "(())", and concatenated structures like "()()". These cover the three scoring rules: atomic, nested, and sequential.

Approaches

The brute-force approach would be a recursive solution that parses the string by finding matching parentheses and calculating scores based on the rules. For every substring, it would recursively compute its score either as 1 for "()" or 2 * score(A) for (A). The problem with this approach is that substring operations can take O(n) time each, leading to an overall complexity of O(n²) or worse, which is inefficient even for moderate string lengths. It works correctly but is not optimal.

The optimal approach relies on using a stack to track scores at different levels of nesting. As we traverse the string:

1. When we encounter '(', we push a 0 to represent the start of a new scope.
2. When we encounter ')', we pop the top value. If it is 0, this represents a simple "()" and contributes 1. Otherwise, it represents a nested score, and we multiply it by 2.
3. We add this computed score to the value at the top of the stack (which represents the outer level).

This works efficiently in linear time and avoids repeated string slicing.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Recursively slice string and compute scores
Stack-based Optimal	O(n)	O(n)	Use stack to track current level scores; single pass

Algorithm Walkthrough

1. Initialize a stack with a single element 0. This represents the score at the outermost level.
2. Iterate through each character in the string s.
3. If the character is '(', push a 0 onto the stack. This signals a new nested level starting.
4. If the character is ')', pop the top element from the stack. Let this popped value be v.

• If v is 0, the parentheses just closed is "()", which scores 1.
• If v is greater than 0, the parentheses enclosed some nested string and scores 2 * v.

5. Add the calculated score to the new top of the stack. This updates the score of the containing level.
6. After processing all characters, the stack contains only one element, which is the total score of the string.

Why it works: The stack invariant ensures that the top of the stack always holds the score of the current nesting level. By pushing a placeholder 0 on '(' and updating the parent level on ')', we correctly handle nested and sequential structures while maintaining linear complexity.

Python Solution

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]  # Initialize stack with outermost level score
        for char in s:
            if char == '(':
                stack.append(0)  # Start a new score frame
            else:
                v = stack.pop()
                stack[-1] += 1 if v == 0 else 2 * v  # Update parent level
        return stack[0]

In this implementation, stack keeps track of scores at each nested level. Every '(' signals the start of a new nested frame, while ')' ends it. The conditional 1 if v == 0 else 2 * v handles both atomic "()" and nested (A) cases. The stack ensures that sequential structures automatically sum their scores because the addition happens at the parent frame level.

Go Solution

func scoreOfParentheses(s string) int {
    stack := []int{0}  // Initialize stack with outermost level
    for _, ch := range s {
        if ch == '(' {
            stack = append(stack, 0)  // Start new frame
        } else {
            v := stack[len(stack)-1]
            stack = stack[:len(stack)-1]  // Pop top
            if v == 0 {
                stack[len(stack)-1] += 1  // Atomic "()"
            } else {
                stack[len(stack)-1] += 2 * v  // Nested "(A)"
            }
        }
    }
    return stack[0]
}

In Go, slices are used as the stack. Appending and slicing simulate push and pop operations. Unlike Python, we must explicitly slice the stack to pop elements. The logic is identical, and the conditional ensures both atomic and nested structures are scored correctly.

Worked Examples

Example 1: "()"

Step	Char	Stack	Action
1	(	[0,0]	push 0
2	)	[1]	pop 0, v=0 → add 1 to parent
End		[1]	return 1

Example 2: "(())"

Step	Char	Stack	Action
1	(	[0,0]	push 0
2	(	[0,0,0]	push 0
3	)	[0,2]	pop 0, v=0 → add 1 × 2? Actually: v=0 → add 1 → [0,1]
4	)	[2]	pop 1, v=1 → add 2*1=2 → [2]
End		[2]	return 2

Example 3: "()()"

Step	Char	Stack	Action
1	(	[0,0]	push 0
2	)	[1]	pop 0 → add 1
3	(	[1,0]	push 0
4	)	[2]	pop 0 → add 1
End		[2]	return 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the string, constant time per character
Space	O(n)	Stack can grow up to depth equal to maximum nesting

Because the stack grows with nesting depth, the space is proportional to the maximum parentheses depth, not the string length in typical scenarios, but in worst case with all nested, O(n).

Test Cases

# Provided examples
assert Solution().scoreOfParentheses("()") == 1  # Simple atomic
assert Solution().scoreOfParentheses("(())") == 2  # Nested
assert Solution().scoreOfParentheses("()()") == 2  # Sequential

# Edge cases
assert Solution().scoreOfParentheses("((()))") == 4  # Deeply nested
assert Solution().scoreOfParentheses("()()()") == 3  # Multiple sequential
assert Solution().scoreOfParentheses("(()(()))") == 6  # Mix nested + sequential
assert Solution().scoreOfParentheses("(((((())))))") == 16  # Maximum nesting within limits

Test	Why
"()"	Simple atomic pair
"(())"	Single nested pair
"()()"	Multiple sequential pairs
"((()))"	Deep nesting
"()()()"	Multiple sequential pairs
"(()(()))"	Mix of nested and sequential
"(((((())))))"	Maximum depth within input constraints

Edge Cases

The first edge case is a string consisting entirely of sequential "()" pairs like "()()()". This tests whether the algorithm correctly sums multiple top-level scores. The stack ensures that sequential scores accumulate in the outer frame.

The second edge case is deeply nested parentheses like "(((())))". This verifies that the algorithm correctly doubles scores at each level of nesting. By pushing a 0 for each '(' and multiplying by 2 when ')' is encountered, the algorithm maintains the correct scoring rule.

The third edge case is a mixed structure like "(()(()))". This tests that nested and sequential rules interact properly. The stack-based solution naturally handles this