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:

1
2

Input: s = "()"
Output: 1

Example 2:

1
2

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

Example 3:

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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:

1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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)