What is the time complexity of Score of Parentheses?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Score of Parentheses?

This problem uses String, Stack. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Score of Parentheses?

Insight 1: The depth of parentheses nesting determines the multiplier. Each '(' increases depth, and each ')' decreases it. Insight 2: Whenever we encounter a ')' immediately after a '(', it represents a '()' sub-string, and its value depends on the current depth.

Which companies ask LeetCode 856. Score of Parentheses in interviews?

This problem is frequently asked at Mountblue, Snap.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Score of Parentheses - LeetCode 856 Solution

Q: How to solve Score of Parentheses?

The solution maintains a 'depth' variable to track the current nesting level. When an opening parenthesis '(' is encountered, the depth is incremented. When a closing parenthesis ')' is encountered, the depth is decremented. If the previous character was an opening parenthesis, it indicates that a '()' sub-string has been found at the current depth. The score is then increased by 2 to the power of the current depth (which is equivalent to 1 << depth). This directly computes the score according to the problem's recursive rules without explicitly using recursion or stack.

Score of Parentheses - Complete Solution Guide

Score of Parentheses is LeetCode problem 856, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 par

Detailed Explanation

The problem asks us to calculate the score of a balanced parentheses string based on the given rules: '()' has a score of 1, 'AB' has a score of A + B, and '(A)' has a score of 2 * A. The input is guaranteed to be a balanced parentheses string containing only '(' and ')', and the length of the string is between 2 and 50. We need to return the integer score of the input string.

Solution Approach

The solution maintains a 'depth' variable to track the current nesting level. When an opening parenthesis '(' is encountered, the depth is incremented. When a closing parenthesis ')' is encountered, the depth is decremented. If the previous character was an opening parenthesis, it indicates that a '()' sub-string has been found at the current depth. The score is then increased by 2 to the power of the current depth (which is equivalent to 1 << depth). This directly computes the score according to the problem's recursive rules without explicitly using recursion or stack.

Step-by-Step Algorithm

Step 1: Initialize `score` and `depth` to 0.
Step 2: Iterate through the input string `s`.
Step 3: If the current character `s[i]` is '(', increment `depth`.
Step 4: If the current character `s[i]` is ')', decrement `depth`.
Step 5: If the previous character `s[i-1]` was '(', add `1 << depth` to `score`. This is equivalent to 2 raised to the power of `depth`.
Step 6: After iterating through the entire string, return the final `score`.

Key Insights

Insight 1: The depth of parentheses nesting determines the multiplier. Each '(' increases depth, and each ')' decreases it.
Insight 2: Whenever we encounter a ')' immediately after a '(', it represents a '()' sub-string, and its value depends on the current depth.
Insight 3: Instead of using recursion or stack to simulate the process described in the problem statement, we can utilize the depth to directly compute the score.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: String, Stack.

Companies

Asked at: Mountblue, Snap.

Score of Parentheses | LeetCode 856

Medium

String Stack

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int scoreOfParentheses(String s) {
        int score = 0;
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                depth += 1;
            } else {
                depth -= 1;
                if (s.charAt(i - 1) == '(') {
                    score += 1 << depth;
                }
            }
        }
        return score;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 856: Score of Parentheses - Detailed explanation and solution approaches.

Topics

String Stack

Companies

MountblueSnap

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:856

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize `score` and `depth` to 0.
2
Step 2: Iterate through the input string `s`.
3
Step 3: If the current character `s[i]` is '(', increment `depth`.
4
Step 4: If the current character `s[i]` is ')', decrement `depth`.
5
Step 5: If the previous character `s[i-1]` was '(', add `1 << depth` to `score`. This is equivalent to 2 raised to the power of `depth`.
6
Step 6: After iterating through the entire string, return the final `score`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the input string once, performing a constant number of operations for each character. Therefore, the time complexity is linear with respect to the length of the string. The algorithm uses a fixed number of variables (score, depth, i), regardless of the input string's length, so the space complexity is constant.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Stack-based Approach

Use a stack to keep track of the scores of the sub-strings. When encountering a '(', push 0 onto the stack. When encountering a ')', pop the last element (sub-string score) from the stack and add it to the score of the previous sub-string (the new last element after the pop). If the popped score is 0, it means it was '()', so add 1 to the previous score. Finally, multiply the previous score by 2 to account for the '()' around it.

Time: O(n)Space: O(n) in worst case

Trade-offs: Stack-based approach provides a more intuitive representation of the recursive rules, but uses O(n) space due to the stack, while current depth-based approach has constant space complexity O(1). So, if memory is a constraint and the input string is large, the depth-based approach is preferred.

✨

Key Insights

1Insight 1: The depth of parentheses nesting determines the multiplier. Each '(' increases depth, and each ')' decreases it.
2Insight 2: Whenever we encounter a ')' immediately after a '(', it represents a '()' sub-string, and its value depends on the current depth.
3Insight 3: Instead of using recursion or stack to simulate the process described in the problem statement, we can utilize the depth to directly compute the score.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input "()". The solution correctly computes the score as 1. Depth is initially 0. When '(' is encountered, depth becomes 1. When ')' is encountered, depth becomes 0. Since the previous character was '(', score becomes 1 << 0 = 1.
Edge case 2: Input "(())". The solution correctly computes the score as 2. Initial depth is 0. First '(': depth = 1. Second '(': depth = 2. First ')': depth = 1. Previous was '(', score += 1 << 1 = 2. Second ')': depth = 0. Previous wasn't '(', so no score added.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering the depth of the parentheses when calculating the score. For example, assuming every '()' has a score of 1, regardless of how deeply nested it is.

✗Common mistake 2: Failing to handle edge cases correctly, such as when the input string is empty or contains mismatched parentheses (though the problem statement guarantees a balanced string).

✗Common mistake 3: Incorrectly applying the rules. For example, attempting to simply count the number of '()' instances and misinterpreting how nesting affects the score.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Parsing and evaluating mathematical expressions, where parentheses dictate the order of operations. The depth concept is analogous to the nesting levels of operators.

🏦Real-world scenario 2: In compiler design, analyzing the structure and scope of code blocks enclosed in parentheses or braces, which have similar hierarchical relationships.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Score of Parentheses"?

For this medium-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?