Score of Parentheses - Video Solutions

Problem Overview: Given a balanced parentheses string, compute its score using three rules: () = 1, AB = A + B (concatenation adds scores), and (A) = 2 * A (nesting doubles the score). You need to evaluate the structure of the string efficiently without explicitly building a parse tree.

The problem is essentially about tracking nesting levels and combining scores correctly while scanning the string. Most solutions rely on either a stack to simulate nested structures or a clever depth-based observation while iterating through the string.

Approach 1: Stack-Based Solution (O(n) time, O(n) space)

Use a stack to keep track of scores for each open parenthesis. When you see (, push the current accumulated score onto the stack and reset the current score to 0. When you encounter ), pop the previous score from the stack and combine it with the current value using the rule prev + max(2 * curr, 1). The key insight: () produces a score of 1, while nested expressions double their inner value. This mirrors how recursive evaluation would work but avoids recursion by using a stack. Prefer this approach when you want a clear structural simulation of nested parentheses.

Approach 2: Iterative with Depth Tracking (O(n) time, O(1) space)

This approach avoids a stack by tracking the current nesting depth while scanning the string once. Every time you encounter the pattern (), it contributes 2^depth to the total score, where depth is the number of open parentheses before the pair closes (after decrementing for the closing bracket). Maintain a depth counter: increment on (, decrement on ). When a closing parenthesis immediately follows an opening one, add 1 << depth to the result. The insight is that each primitive pair contributes based on how deeply it is nested. This method is extremely space efficient and often considered the most elegant solution.

Recommended for interviews: The stack-based method demonstrates a solid understanding of nested structure evaluation and is straightforward to reason about during whiteboard interviews. The depth-tracking approach is the optimized version with O(1) extra space and shows deeper insight into how parentheses scoring works internally. Walking through both approaches during discussion signals strong problem-solving depth.