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.

Description Solution Video 8:52

856. Score of Parentheses

Medium66.0% acceptance5 companies

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.

Asked at 5 companies

Tiktok Meta

Google Amazon Bloomberg

Topics

Stack String

8:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def scoreOfParentheses(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"()"

Input

"(())"

Input

"()()"

Your code is saved on this device.Solution