LeetCode 856: Score of Parentheses

Problem

LeetCode 856: Score of Parentheses (Medium)

Problem Statement: You are given a string containing only the characters ( and ). The parentheses are guaranteed to be balanced (as in syntactically valid source code). Calculate a score using the following rules:

• () has a score of 1.
• AB has a score of A + B, where A and B are balanced strings of parentheses.
• (A) has a score of 2 * A, where A is a balanced string of parentheses.

Solution

In the problem LeetCode 20: Valid Parentheses, we have to check if a string of parentheses is balanced. In this problem, the input is guaranteed to be balanced, so we don’t need to verify that condition. But some of the techniques used to verify balance are also useful in this problem.

Given the recursive definition in the problem statement, it seems like the problem might lend itself to a recursive solution. The free official solution uses a recursive function in Approach 1, which requires $O(n^2)$ time and $O(n)$ space. Balanced parentheses problems can also generally be solved using a stack, which is how it’s done in Approach 2. That solution reduces the time requirement to $O(n)$. I’m going to explain Approach 3, which uses no stack or other data structures, and requires only $O(1)$ space.

Solution idea

Define a core as the substring (). A core has a score of 1. When a core is surrounded by parentheses, each set of surrounding parentheses multiplies what’s inside by 2. So () is 1, (()) is 2, ((())) is 4, and so on. If two or more substrings are arranged side by side, their scores are added together. So ()() is $1+1=2$, ()()() is $1+1+1=3$, and (())(())(()) is $2+2+2=6$. Because of these rules, the total score can always be expressed as the sum of powers of two.

Next, define the balance of a substring as the number of opening parentheses in the substring minus the number of closing parentheses. The balance of the full input string is always 0. But if we iterate through the input string character by character, we can increment the balance at each ( and decrement it at each ), and the balance at each step will be a non-negative integer that we can use to calculate a running score.

Here’s the key idea: Whenever we see () (a core), we increase the current score by $2^b$, where $b$ is the current balance. This works because $b$ is the number of parentheses the core is contained in, and each of those parentheses multiplies the core value by $2$. So for (()), we’ll have $b=1$ when we encounter the core, so we’ll correctly evaluate the score as $2^1=2$. For (())(())(()), we’ll have $b=1$ at each core, so we’ll add $2$ to the score three times.

A quick note on code syntax: 1 << b means start with 1 and shift it left b times. So it’s the same as $2^b$ or Math.Pow(2, b).

Pseudocode

Variables (both ints, initialized to zero):

• score: the problem result

• balance: the current balance of parentheses

  for each char c in input string
      if c is a left paren, increment balance
      else
          decrement balance
          if the previous char was a left paren
              increment score by 2^balance
  return score
  

As described in the solution idea, we iterate through the input one character at a time, incrementing the current balance when we see ( and decrementing it when we see ). Also, when we see (), we increase the result by 2 raised to the power of the current balance.

Code

Score of Parentheses on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.