By Long Luo

This article is the solution The Tricky and Clean Solution: Replace Core by 1 of Problem 856. Score of Parentheses.

There are many approaches about this problem, like Stack, Divide and Conquer, Count Cores and so on. Here shows a Tricky and Clean solution.

Intuition

The sum will be a sum of powers of \(2\), as every core (a substring \(()\), with score \(1\) ) will have it’s score multiplied by \(2\) for each exterior set of parentheses that contains that core.

Since \(s\) is a balanced parentheses string, we can replace \(()\) by \(1\), then the result is still a balanced parentheses string.

For example, \((()())\) will become \((1(1))\). The sum is \((1 + 1 \times 2) \times 2 = 1 \times 2 + 1 \times 2 \times 2 = 6\).

As a result, let \(base = 1\), we can make \(base = base \times 2\) when we meet \((\), \(base = base \div 2\) when we meet \((\), and add \(1\) when we meet \(1\).

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

class Solution {
    public int scoreOfParentheses(String s) {
        s = s.replace("()", "1");

        int ans = 0;
        int base = 1;

        for (char ch : s.toCharArray()) {
            switch (ch) {
                case '(':
                    base *= 2;
                    break;

                case ')':
                    base /= 2;
                    break;

                default:
                    ans += base;
                    break;
            }
        }

        return ans;
    }
}

Analysis

• Time Complexity: \(O(n)\).
• Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗