We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Score of Parentheses

Number: 886

Difficulty: Medium

Paid? No

Companies: Meta, TikTok, Bloomberg, Microsoft, Snap, Amazon, Google

Problem Description

Given a balanced parentheses string s, calculate the score of the string based on these rules:

  1. "()" has score 1.
  2. For two balanced strings A and B, the score of AB is A + B.
  3. For a balanced string A enclosed in parentheses "(A)", the score is 2 * A.

Key Insights

  • Use a stack to process the parentheses structure.
  • When encountering a closing parenthesis, check if it directly forms "()", assign score 1; otherwise, accumulate the inner score.
  • Multiply the accumulated score by 2 when a nested structure is detected.
  • The algorithm processes the string in one pass, handling nesting and direct pairs efficiently.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because each character is processed once. Space Complexity: O(n), for the stack used in worst-case scenarios with nested parentheses.

Solution

Utilize a stack to keep track of intermediate scores. When encountering an opening parenthesis '(', push a marker (or a 0) onto the stack to indicate the start of a new sub-expression. When you encounter a closing parenthesis ')', pop values from the stack until you reach the marker:

  • If the marker is immediately encountered, it means the parentheses form "()", so assign a score of 1.
  • Otherwise, the popped values represent the score inside a nested structure; multiply it by 2 for the current level. Push the computed score back onto the stack. Finally, sum all values in the stack to get the final score.

Code Solutions

# Python solution for calculating the score of parentheses
def scoreOfParentheses(s: str) -> int:
    stack = []  # stack to hold scores and markers
    for char in s:
        if char == '(':
            # push marker to denote a new nested group starting
            stack.append('(')
        else:
            # we encountered a closing parenthesis, process the group
            if stack[-1] == '(':
                # direct "()" pattern found, replace marker with score 1
                stack.pop()  # remove the '(' marker
                stack.append(1)  # push the score for "()"
            else:
                # calculate score for nested structure
                curr_score = 0
                # accumulate inner scores until we find the matching '('
                while stack[-1] != '(':
                    curr_score += stack.pop()
                stack.pop()  # remove the matching '('
                # push the doubled score for nested group
                stack.append(2 * curr_score)
    # sum all scores on the stack (handles concatenated groups)
    return sum(stack)

# Example usage:
#print(scoreOfParentheses("(()(()))"))
← Back to All Questions