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.
Example 1:
Input: s = "()" Output: 1
Example 2:
Input: s = "(())" Output: 2
Example 3:
Input: s = "()()" Output: 2
Constraints:
2 <= s.length <= 50s consists of only '(' and ')'.s is a balanced parentheses string.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.
This approach leverages a stack to manage the scores of the balanced parentheses string. As we iterate through the string:
At the end of the iteration, the top of the stack will contain the total score.
The C solution utilizes a simple stack array to keep track of scores at each level. As we parse the string, we push zero onto the stack for each '('. When encountering a ')', the score is calculated and added to the top of the stack. This method ensures that nested structures are calculated accurately by collapsing scores upwards through multiplication and addition.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the stack usage that can store one element per character in the worst case.
This approach iteratively computes the score by tracking the depth of parentheses:
In C, this iterative approach uses an array to track scores at different depths. It handles the transition from '(' to ')' by either recognizing single pairs or multiplying for nested structures. This approach exploits direct index manipulation for score calculations.
Time Complexity: O(n), dictated by the string length.
Space Complexity: O(1), since the depth array size is fixed by constraint.
By observing, we find that () is the only structure that contributes to the score, and the outer parentheses just add some multipliers to this structure. So, we only need to focus on ().
We use d to maintain the current depth of parentheses. For each (, we increase the depth by one, and for each ), we decrease the depth by one. When we encounter (), we add 2^d to the answer.
Let's take (()(())) as an example. We first find the two closed parentheses () inside, and then add the corresponding 2^d to the score. In fact, we are calculating the score of (()) + ((())).
( ( ) ( ( ) ) )
^ ^ ^ ^
( ( ) ) + ( ( ( ) ) )
^ ^ ^ ^
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string.
Related problems about parentheses:
| Approach | Complexity |
|---|---|
| Stack-Based Solution | Time Complexity: O(n), where n is the length of the string. |
| Iterative with Depth Tracking | Time Complexity: O(n), dictated by the string length. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Solution | O(n) | O(n) | Best for understanding nested evaluation and implementing a direct simulation of parentheses structure |
| Iterative with Depth Tracking | O(n) | O(1) | Preferred when minimizing memory usage and recognizing the depth-based scoring pattern |
LeetCode 856. Score of Parentheses (Algorithm Explained) • Nick White • 16,657 views views
Watch 9 more video solutions →Practice Score of Parentheses with our built-in code editor and test cases.
Practice on FleetCode