Score of Parentheses

Problem

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.

Examples

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

Follow up

Can you solve it in O(1) space?

Solution

Method 1 - Using Recursion

The problem can be solved using recursion by breaking down the string into smaller parts and calculating scores based on the rules.

Approach

1. Base Case: If the string is empty, return a score of 0.
2. Recursive Case:
   • Initialize a balance counter and a local score to keep track of the current substring's score.
   • Traverse the string and adjust the balance counter based on encountering an opening or closing parenthesis.
   • When the balance counter returns to zero, it indicates a closed section of the string:
     1. If the section is "()", it contributes a score of 1.
     2. Otherwise, it contributes 2 * score(inner_section).
   • Sum these scores to get the total score for the string.

Code

Java

class Solution {
    public int scoreOfParentheses(String s) {
        return score(s, 0, s.length());
    }

    private int score(String s, int start, int end) {
        int balance = 0;
        int result = 0;

        for (int i = start; i < end; i++) {
            if (s.charAt(i) == '(') {
                balance++;
            } else {
                balance--;
            }

            // When balance equals zero, it means we have a balanced substring
            if (balance == 0) {
                if (i - start == 1) {
                    // This is a "()" pair
                    result++;
                } else {
                    // This is a (A) structure
                    result += 2 * score(s, start + 1, i);
                }
                start = i + 1;
            }
        }

        return result;
    }
}

Python

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        return self.score(s, 0, len(s))
    
    def score(self, s: str, start: int, end: int) -> int:
        balance = 0
        result = 0

        i = start
        while i < end:
            if s[i] == '(':
                balance += 1
            else:
                balance -= 1

            # When balance equals zero, it means we have a balanced substring
            if balance == 0:
                if i - start == 1:
                    # This is a "()" pair
                    result += 1
                else:
                    # This is a (A) structure
                    result += 2 * self.score(s, start + 1, i)
                start = i + 1
            
            i += 1

        return result

Complexity

• ⏰ Time complexity: O(n), where n is the length of the string, since each character is processed once.
• 🧺 Space complexity: O(n), due to the recursive call stack.

Method 2- Using Stack

We can instead use the stack. Let curr records the score at the current layer.

Then, we can go to characters of string, and

• When we encounter '(', the current score is pushed to the stack, and curr is reset to 0 as we enter a new inner layer.
• When we encounter ')', the curr score is doubled (minimum 1), we exit the current layer, and update curr to the value from the stack plus the curr score.

Code

Java

class Solution {
    public int scoreOfParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        int curr = 0;

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(curr);
                curr = 0;
            } else {
                curr = stack.pop() + Math.max(curr * 2, 1);
            }
        }

        return curr;
    }
}

Python

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = []
        curr = 0
        
        for ch in s:
            if ch == '(':
                stack.append(curr)
                curr = 0
            else:
                curr = stack.pop() + max(curr * 2, 1)
        
        return curr

Complexity

• ⏰ Time complexity: O(n), where n is the length of the string, as each character is processed once.
• 🧺 Space complexity: O(n), due to the stack storing scores for nested parentheses layers.

Method 3 - Using Array

Similar to the stack approach, we use an array to maintain scores, but instead of pushing and popping elements, we use a pointer to navigate through levels.

Code

Java

class Solution {
    public int scoreOfParentheses(String s) {
        int[] ans = new int[30];
        int pointer = 0;

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                ans[++pointer] = 0;
            } else {
                ans[pointer - 1] += Math.max(ans[pointer--] * 2, 1);
            }
        }

        return ans[0];
    }
}

Python

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = [0] * 30
        pointer = 0

        for ch in s:
            if ch == '(':
                pointer += 1
                ans[pointer] = 0
            else:
                ans[pointer - 1] += max(ans[pointer] * 2, 1)
                pointer -= 1

        return ans[0]

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)

Method 4 - Using Counter In O(1) Space

We count the number of layers (l):

• If we encounter '(' we increment layers ⇨ l++
• else we encounter ')', we decrement layers number ⇨ l--
  • If we encounter a pair "()", we know the number of layer outside, so we can calculate the score res += Math.pow(2,l)

Consider the example:

str =    (   (   (   (   )  (   )  (   )   )  )  )
depth =  1   2   3   4   3  4   3  4   3   2  1  0
ans =                    8      8      8

Final result = 8 + 8 + 8 = 24

Decrementing l when encountering ) accounts for the intermediate () lying at depth l-1.

eg: ( ( ( **( )** - this valid pair lies at depth 3.

Code

Java

class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0, l = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                l++;
            } else {
                l--;
                if (s.charAt(i - 1) == '(') {
                    ans += 1 << l; // equivalent to Math.pow(2, l)
                }
            }
        }
        return ans;
    }
}

Python

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = 0
        l = 0
        for i in range(len(s)):
            if s[i] == '(':
                l += 1
            else:
                l -= 1
                if s[i - 1] == '(':
                    ans += 1 << l # equivalent to 2**l
        return ans

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)