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.The key idea in #856 Score of Parentheses is to interpret how balanced parentheses contribute to a final score. According to the rules, a pair () has score 1, concatenation adds scores, and wrapping a valid sequence inside parentheses doubles its score. This structure makes the problem ideal for a stack-based approach or a depth tracking technique.
Using a stack, you push intermediate scores whenever a new ( is encountered. When a closing ) appears, compute the score of the enclosed segment and combine it with the previous value. This mimics how nested expressions are evaluated.
An alternative optimized idea tracks the current depth of parentheses. Whenever you encounter a primitive pair (), its contribution depends on the nesting level, allowing you to accumulate the score efficiently without storing full segments.
Both strategies process the string once, making them efficient for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based evaluation | O(n) | O(n) |
| Depth counting optimization | O(n) | O(1) |
NeetCode
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.
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.
1import java.util.Stack;
2
3public class Solution {
4 public static int scoreOfParentheses(String s) {
5
In this Java solution, the stack is used to keep track of the score at each level. When a ')' is encountered, the score at that level is evaluated and then added to the previous level's score. This approach effectively manages nested and sequential parentheses scores.
This approach iteratively computes the score by tracking the depth of parentheses:
Time Complexity: O(n), dictated by the string length.
Space Complexity: O(1), since the depth array size is fixed by constraint.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of parentheses parsing problems frequently appear in FAANG-style interviews. They test understanding of stacks, string processing, and recognizing patterns in nested structures.
Yes, it can be solved using a depth counter. By tracking how deeply nested you are and detecting primitive pairs "()", you can add scores using bit shifting based on the current depth.
A stack is the most intuitive data structure for this problem. It helps track nested parentheses and partial scores, allowing you to combine values as closing brackets appear.
The optimal approach is usually a depth-based or stack-based solution. A stack simulates nested evaluation, while the depth-counting trick computes contributions of primitive pairs in a single pass. Both achieve O(n) time complexity.
Using a list to simulate depth, this Python solution tracks scores with manipulations based on the transitions from open to close parentheses. Resetting higher depth scores ensures accuracy in nested parentheses calculations.