Problem Statement: You are given a string containing only the characters
). 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.
ABhas a score of
A + B, where
Bare balanced strings of parentheses.
(A)has a score of
2 * A, where
Ais a balanced string of parentheses.
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.
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
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.
LeetCode Model Solutions
I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.