#856

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Score of Parentheses

Calculate the score of a balanced parentheses string using stack-based state management for an optimal solution.

Problem Statement

Given a balanced parentheses string s, return its score. The score of a balanced parentheses string is calculated as follows: If the string is '()', the score is 1. For more complex structures like '(())', the score is double the inner score, while a string like '()()' adds the individual scores together.

The problem can be solved using stack-based state management. As we traverse the string, we use the stack to store temporary scores and process nested structures efficiently. The score is accumulated and adjusted based on the depth and structure of the parentheses.

Examples

Example 1

Input: s = "()"

Output: 1

Example details omitted.

Example 2

Input: s = "(())"

Output: 2

Example details omitted.

Example 3

Input: s = "()()"

Output: 2

Example details omitted.

Constraints

2 <= s.length <= 50
s consists of only '(' and ')'.
s is a balanced parentheses string.

Solution Approach

Stack-based Score Calculation

Use a stack to keep track of scores for each level of nested parentheses. Each time a new pair is encountered, push the score onto the stack, adjusting the score based on nested levels.

Double the Score for Nested Structures

When encountering a closing parenthesis, the score of the most recent nested structure is doubled. Add it to the current score or combine it as needed depending on the depth.

Accumulate and Return the Final Score

The score is calculated as we go along. At the end of the string, the final score is obtained by summing up all the individual scores from the stack.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the final approach. A stack-based approach generally runs in O(n) time, where n is the length of the string, and uses O(n) space for the stack.

What Interviewers Usually Probe

Look for an efficient stack-based solution to manage nested structures.
Evaluate how the candidate handles multiple nested parentheses and their score computation.
Focus on correct state management using the stack, ensuring the solution works for all string lengths.

Common Pitfalls or Variants

Common pitfalls

Mismanaging nested parentheses by not properly doubling the inner score.
Forgetting to add the scores when encountering non-nested parentheses like '()()'.
Incorrect stack operations that lead to incorrect score accumulation.

Follow-up variants

Modify the problem to handle non-balanced parentheses strings and test for validity.
Optimize the solution to handle larger strings by managing stack size more effectively.
Consider variations where parentheses are nested with different operations or values.

FAQ

What is the primary pattern used to solve the Score of Parentheses problem?

The primary pattern used in this problem is stack-based state management to track scores as we traverse the parentheses string.

How do you handle nested parentheses in the Score of Parentheses problem?

Nested parentheses are handled by doubling the score of the inner structure when the corresponding closing parenthesis is encountered.

What is the time complexity of solving the Score of Parentheses problem?

The time complexity is O(n), where n is the length of the parentheses string, due to the single pass through the string.

What are some common pitfalls when solving the Score of Parentheses problem?

Common pitfalls include mismanaging nested parentheses, failing to add scores for non-nested structures, and incorrect stack operations.

How does GhostInterview assist with the Score of Parentheses problem?

GhostInterview helps by guiding stack operations, optimizing solutions, and providing hints for handling nested structures and edge cases.

terminal

Solution

Solution 1: 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 `()`.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = d = 0
        for i, c in enumerate(s):
            if c == '(':
                d += 1
            else:
                d -= 1
                if s[i - 1] == '(':
                    ans += 1 << d
        return ans

Continue Practicing

#844 backspace string compare #880 decoded string at index #921 minimum add to make parentheses valid