Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Score of Parentheses solution and explanation

MediumStackString6 min read66.0% acceptanceUpdated 9 Apr 2026
Asked atTiktokMetaGoogleAmazonBloomberg
Practise Score of Parentheses
8:52
LeetCode 856. Score of Parentheses (Algorithm Explained)Nick White · 8:52 · 16K viewsWatch on YouTube
9 more videos on this problem
  1. LeetCode 856. Score of Parentheses (Algorithm Explained)Nick White · 8:52 · 16K views
  2. Score of Parentheses | LeetCode 856Pepcoding · 21:50 · 13K views
  3. Score of Parentheses | Live Coding with Explanation | Leetcode - 856Algorithms Made Easy · 9:27 · 8K views
  4. Leetcode 856. Score of ParenthesesFraz · 16:40 · 5K views
  5. Score of Parentheses | Leetcode 856 | 2 approaches | Stack | Day-17Ayushi Sharma · 24:51 · 4K views
  6. Leetcode - Score of Parentheses (Python)Timothy H Chang · 9:14 · 3K views
  7. Score of Parentheses | Leetcode 856Coding Decoded · 13:38 · 1K views
  8. leetcode 856. Score of Parenthesesalgorithm everyday · 11:37 · 738 views
  9. Daily Leetcode #716: Mar 17, 2022 - 856. Score of ParenthesesProgramming Live with Larry · 11:24 · 532 views
  10. LeetCode | 856. Score of Parentheses | StackCompl3x · 13:42 · 457 views

The problem

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.

def score_of_parentheses(s):
    stack = [0]
    for ch in s:
        if ch == '(':  
            stack.append(0)
        else:
            score = stack.pop()
            stack[-1] += max(2 * score, 1)
    return stack.pop()

if __name__ == "__main__":
    s = "(())"
    print("Score:", score_of_parentheses(s))
import java.util.Stack;

public class Solution {
    public static int scoreOfParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // Base score

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(0);
            } else {
                int score = stack.pop();
                int prevScore = stack.pop();
                stack.push(prevScore + (score > 0 ? 2 * score : 1));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String s = "(())";
        System.out.println("Score: " + scoreOfParentheses(s));
    }
}
#include <iostream>
#include <stack>
#include <string>

int scoreOfParentheses(std::string s) {
    std::stack<int> st;
    st.push(0); // Base score
    
    for (char ch : s) {
        if (ch == '(') {
            st.push(0);
        } else {
            int score = st.top(); st.pop();
            int prevScore = st.top(); st.pop();
            st.push(prevScore + (score > 0 ? 2 * score : 1));
        }
    }
    return st.top();
}

int main() {
    std::string s = "(())";
    std::cout << "Score: " << scoreOfParentheses(s) << std::endl;
    return 0;
}
function scoreOfParentheses(s) {
    const stack = [0]; // Base score

    for (const ch of s) {
        if (ch === '(') {
            stack.push(0);
        } else {
            const score = stack.pop();
            stack[stack.length - 1] += Math.max(2 * score, 1);
        }
    }

    return stack.pop();
}

console.log("Score:", scoreOfParentheses("(())"));
#include <stdio.h>
#include <stdlib.h>

int scoreOfParentheses(char *s) {
    int stack[50]; // Constraint allows for up to 50
    int top = -1;
    stack[++top] = 0; // Start with a base score
    
    while (*s) {
        if (*s == '(') {
            stack[++top] = 0;
        } else {
            int score = stack[top--];
            stack[top] += (score > 0 ? 2 * score : 1);
        }
        s++;
    }
    return stack[0];
}

int main() {
    char s[] = "(())";
    printf("Score: %d\n", scoreOfParentheses(s));
    return 0;
}
using System;
using System.Collections.Generic;

public class Program
{
    public static int ScoreOfParentheses(string s)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(0); // Base score

        foreach (char ch in s)
        {
            if (ch == '(')
            {
                stack.Push(0);
            }
            else
            {
                int score = stack.Pop();
                stack.Push(stack.Pop() + Math.Max(2 * score, 1));
            }
        }

        return stack.Pop();
    }

    public static void Main()
    {
        string s = "(())";
        Console.WriteLine("Score: " + ScoreOfParentheses(s));
    }
}

The Python solution uses a list as a stack to manage parentheses scores. For each closing parenthesis, it calculates the intermediate score, updates the previous level's score, and handles nested structures by doubling when necessary. This ensures accurate score calculation throughout nested levels.

Complexity

Time Complexity: O(n), with n being the length of the string.
Space Complexity: O(n), due to the list used as a stack.

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.
def score_of_parentheses(s):
    score = [0] * 50
    depth = 0
    
    for i in range(len(s)):
        if s[i] == '(':  
            depth += 1
        else:
            depth -= 1
            if s[i - 1] == '(':  
                score[depth] += 1
            else:
                score[depth] += 2 * score[depth + 1]
            score[depth + 1] = 0
    
    return score[0]

if __name__ == "__main__":
    s = "((()))"
    print("Score:", score_of_parentheses(s))
public class Solution {
    public static int scoreOfParentheses(String s) {
        int[] score = new int[50];
        int depth = 0;

        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++depth;
            } else {
                --depth;
                if (s.charAt(i - 1) == '(') {
                    score[depth] += 1;
                } else {
                    score[depth] += 2 * score[depth + 1];
                }
                score[depth + 1] = 0;
            }
        }

        return score[0];
    }

    public static void main(String[] args) {
        String s = "((()))";
        System.out.println("Score: " + scoreOfParentheses(s));
    }
}
#include <iostream>
#include <vector>
#include <string>

int scoreOfParentheses(std::string s) {
    std::vector<int> score(50, 0);
    int depth = 0;

    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '(') {
            ++depth;
        } else {
            --depth;
            if (s[i - 1] == '(') {
                score[depth] += 1;
            } else {
                score[depth] += 2 * score[depth + 1];
            }
            score[depth + 1] = 0;
        }
    }

    return score[0];
}

int main() {
    std::string s = "((()))";
    std::cout << "Score: " << scoreOfParentheses(s) << std::endl;
    return 0;
}
function scoreOfParentheses(s) {
    const score = new Array(50).fill(0);
    let depth = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            depth++;
        } else {
            depth--;
            if (s[i - 1] === '(') {
                score[depth] += 1;
            } else {
                score[depth] += 2 * score[depth + 1];
            }
            score[depth + 1] = 0;
        }
    }

    return score[0];
}

console.log("Score:", scoreOfParentheses("((()))"));
#include <stdio.h>
#include <string.h>

int scoreOfParentheses(char *s) {
    int depthScores[50] = {0}; // Up to depth 50
    int depth = 0;
    
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == '(') {
            depth++;
        } else {
            depth--;
            if (s[i - 1] == '(') {
                depthScores[depth] += 1;
            } else {
                depthScores[depth] += 2 * depthScores[depth + 1];
            }
            depthScores[depth + 1] = 0;
        }
    }
    return depthScores[0];
}

int main() {
    char s[] = "((()))";
    printf("Score: %d\n", scoreOfParentheses(s));
    return 0;
}
using System;

public class Program
{
    public static int ScoreOfParentheses(string s)
    {
        int[] score = new int[50];
        int depth = 0;

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
            {
                depth++;
            }
            else
            {
                depth--;
                score[depth] += s[i - 1] == '(' ? 1 : 2 * score[depth + 1];
                score[depth + 1] = 0;
            }
        }

        return score[0];
    }

    public static void Main()
    {
        string s = "((()))";
        Console.WriteLine("Score: " + ScoreOfParentheses(s));
    }
}

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.

Complexity

Time Complexity: O(n), with one traversal over s.
Space Complexity: O(1), with a constant-sized score list.

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:

func scoreOfParentheses(s string) int {
	ans, d := 0, 0
	for i, c := range s {
		if c == '(' {
			d++
		} else {
			d--
			if s[i-1] == '(' {
				ans += 1 << d
			}
		}
	}
	return ans
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Stack-Based Solution

Time Complexity: O(n), with n being the length of the string.
Space Complexity: O(n), due to the list used as a stack.

Iterative with Depth Tracking

Time Complexity: O(n), with one traversal over s.
Space Complexity: O(1), with a constant-sized score list.

Counting–

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

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.

Comments

Now write it yourselfClose this page and solve Score of Parentheses in the editor, without looking.
Practise Score of Parentheses