Skip to main content
Talentd

Score of Parentheses - Solution & Explanation

MediumStringStack19 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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 <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

Approach Overview

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.

Approach 1: Stack-Based Solution

This approach leverages a stack to manage the scores of the balanced parentheses string. As we iterate through the string:

  • Push 0 onto the stack for every '('.
  • For every ')', pop the top element (score) from the stack and update it. If the popped score is zero, it means it was a simple pair '()', so the score is at least 1. Then, double this score if necessary and add it to the current top of the stack.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative with Depth Tracking

This approach iteratively computes the score by tracking the depth of parentheses:

  • Keep an array or list where the index indicates depth and the value holds the score.
  • Increment the depth for '(', decrease it for ')'.
  • On encountering ')', when at zero depth, update the previous depth's score. If it completes a '()', increment the current score; if it ends a nested structure, double the score.
  • The total score is summed by the end.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), dictated by the string length.
Space Complexity: O(1), since the depth array size is fixed by constraint.

Try this approach in the editor →

Approach 3: Counting

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:

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Solution

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.

Iterative with Depth Tracking

Time Complexity: O(n), dictated by the string length.
Space Complexity: O(1), since the depth array size is fixed by constraint.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based SolutionO(n)O(n)Best for understanding nested evaluation and implementing a direct simulation of parentheses structure
Iterative with Depth TrackingO(n)O(1)Preferred when minimizing memory usage and recognizing the depth-based scoring pattern

Video Solution

LeetCode 856. Score of Parentheses (Algorithm Explained) • Nick White • 16,801 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Score of Parentheses easy or hard?
Score of Parentheses is classified as a Medium difficulty problem. The rules look simple, but translating them into an efficient single-pass algorithm requires understanding nested structures, stack usage, or recognizing the depth-based scoring pattern.
Score of Parentheses Python/Java solution
Python and Java implementations usually follow the same logic: either maintain a stack of scores or track nesting depth during iteration. Both implementations run in O(n) time. Python often uses a list as the stack, while Java typically uses Stack or ArrayDeque.
How to solve Score of Parentheses in O(n)?
Traverse the string once while tracking either nested scores with a stack or the current depth level. For the stack method, push previous scores on '(' and combine results on ')'. For the depth method, detect the pattern () and add 2^depth to the total score. Both strategies compute the result in linear time.
What is the best approach for Score of Parentheses?
The depth-tracking approach is typically considered the best because it runs in O(n) time with O(1) extra space. It scans the string once and adds 2^depth whenever it detects the primitive pattern (). The stack-based solution is also O(n) but uses O(n) space and is often easier to explain during interviews.
Is Score of Parentheses asked at Google/Amazon/Meta?
Score of Parentheses is a common interview-style problem involving stacks and parsing nested structures. Variations of this problem have appeared in interviews at companies like Amazon, Google, and Meta, especially for roles testing stack manipulation and string processing skills.
What data structure is used in Score of Parentheses?
The most common data structure used is a stack. It helps store intermediate scores when entering nested parentheses and restores the previous context when the nesting closes. Some optimized solutions avoid extra structures by tracking only the current nesting depth.
What is the time complexity of Score of Parentheses?
The optimal solutions run in O(n) time where n is the length of the parentheses string. Each character is processed exactly once while updating depth or stack values. Space complexity is O(n) for the stack approach and O(1) for the depth-tracking method.

Ready to solve this problem?

Practice Score of Parentheses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring