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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Score of Parentheses

Difficulty: Medium

Problem Description

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.

Key Insights

  • The scoring rules are nested and recursive in nature.
  • The simplest case, "()", has the lowest score of 1.
  • Nested parentheses increase the score exponentially based on depth.
  • Using a stack data structure helps keep track of the score as we encounter opening and closing parentheses.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string, as we traverse the string once. Space Complexity: O(n) - for the stack that may store all opening parentheses in the worst case.

Solution

To calculate the score of the balanced parentheses string, we can use a stack:

  1. Initialize a stack to keep track of scores.
  2. Traverse each character in the string:
    • If it's an opening parenthesis '(', push a marker (like 0) onto the stack.
    • If it's a closing parenthesis ')', pop from the stack to calculate the score:
      • If the top of the stack is 0, it indicates a simple "()", so we push 1.
      • If the top of the stack is not 0, it means we have a nested structure; we pop the top value, double it (2 * score), and then add it to the score accumulated from previous levels.
  3. Continue this until the end of the string and return the top value of the stack as the final score.

Code Solutions

def scoreOfParentheses(s: str) -> int:
    stack = [0]  # Initialize stack with a base score
    for char in s:
        if char == '(':
            stack.append(0)  # Push a marker for the new level
        else:
            top = stack.pop()  # Calculate the score for the current level
            stack[-1] += max(2 * top, 1)  # If top is 0, it means "()", otherwise it's a nested structure
    return stack[0]  # Final score at the base of the stack
← Back to All Questions