Score of Parentheses - Practice Coding Problems

Score of Parentheses - Problem

String Stack Medium

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rules:

() 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

Input & Output

Example 1 — Basic Nested

$ Input: s = "(())"

› Output: 2

💡 Note: Inner () has score 1, outer parentheses double it: 2 * 1 = 2

Example 2 — Complex Structure

$ Input: s = "(()(()))"

› Output: 6

💡 Note: First () at depth 1 contributes 2¹ = 2, second () at depth 2 contributes 2² = 4, total: 2 + 4 = 6

Example 3 — Simple Concatenation

$ Input: s = "()()"

› Output: 2

💡 Note: Two separate () pairs: 1 + 1 = 2

Constraints

2 ≤ s.length ≤ 50
s consists of only '(' and ')'

Visualization

Tap to expand

Understanding the Visualization

Input

Balanced parentheses string

Process

Apply scoring rules based on structure

Output

Numerical score

Key Takeaway

🎯 Key Insight: Only () pairs contribute to score, each contributing 2^depth where depth is the nesting level

Asked in

G Google 42 M Microsoft 35

The key insight is that only () pairs contribute to the score, each contributing 2^depth. The optimal approach tracks nesting depth and sums contributions in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Parsing	O(n²)	O(n)	Parse the string recursively, calculating scores based on the rules
Stack-Based Approach	O(n)	O(n)	Use a stack to track scores at each nesting level
Depth Counting (Optimal)	O(n)	O(1)	Count contribution of each () pair based on its nesting depth

Recursive Parsing — Algorithm Steps

Parse from left to right
For each balanced substring, recursively calculate its score
Sum scores for concatenated parts
Multiply by 2 for nested parts

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse

Identify balanced substrings

Score

Apply scoring rules recursively

Result

Sum all computed scores

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int index_pos;

int parse(const char* s) {
    int score = 0;
    while (index_pos < strlen(s) && s[index_pos] == '(') {
        index_pos++;
        if (s[index_pos] == ')') {
            score += 1;
            index_pos++;
        } else {
            int inner_score = parse(s);
            score += 2 * inner_score;
            index_pos++; // skip ')'
        }
    }
    return score;
}

int solution(char* s) {
    index_pos = 0;
    return parse(s);
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, each character may be processed multiple times due to recursive calls

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack can go up to depth n in deeply nested cases

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Parsing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler