Score of Parentheses
MedPrompt
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 score1.ABhas scoreA + B, whereAandBare balanced parentheses strings.(A)has score2 * A, whereAis a balanced parentheses string.
Example 1:
Input: s = "()"
Output: 1Example 2:
Input: s = "(())"
Output: 2Example 3:
Input: s = "()()"
Output: 2
Constraints:
2 <= s.length <= 50sconsists of only'('and')'.sis a balanced parentheses string.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the recursive definition of the score into a recursive function. A function score(S) will compute the score of a given balanced parentheses string S. The function determines if S is of the form (A) or A+B and calls itself recursively.
Algorithm
- Define a recursive function
score(s)that takes a strings. - If
sis"()"return 1. - Initialize a balance counter
bal = 0. - Iterate through
sfrom left to right (except the last character) to find a split point. - Update
balfor each character. Ifbalbecomes 0 at indexi, it means we found a split point. The string isA+BwhereA = s.substring(0, i+1)andB = s.substring(i+1). Returnscore(A) + score(B). - If the loop completes without
balbecoming 0, the string is of the form(A).Ais the inner part ofs. Return2 * score(s.substring(1, s.length()-1)).
Walkthrough
The core idea is to implement a function that computes the score of a given string s. To distinguish between the A+B case and the (A) case, we can scan the substring and maintain a balance counter (increment for (, decrement for )). If the balance becomes zero at an index k before the end of the substring, it means the string is composed of two or more adjacent balanced strings. The first one is s.substring(0, k+1) and the rest is s.substring(k+1). The score is then the sum of the scores of these two parts, computed recursively. If the balance never becomes zero until the very end, the string must be of the form (A), where A is the inner substring. The score is 2 * score(A). The base case for the recursion is when the substring is "()", which has a score of 1.
class Solution { public int scoreOfParentheses(String s) { return score(s); } private int score(String s) { if (s.equals("()")) { return 1; } int balance = 0; int splitPoint = -1; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { balance++; } else { balance--; } if (balance == 0 && i < s.length() - 1) { splitPoint = i; break; } } if (splitPoint != -1) { // Case AB: score(A) + score(B) String a = s.substring(0, splitPoint + 1); String b = s.substring(splitPoint + 1); return score(a) + score(b); } else { // Case (A): 2 * score(A) String a = s.substring(1, s.length() - 1); return 2 * score(a); } }}Complexity
Time
O(N^2) to O(N^3). The complexity depends on the structure of the string and the implementation of `substring`. For a string like `((...))`, the recursion is `T(N) = T(N-2) + O(N)`, which solves to `O(N^2)`. If `substring` takes O(N), the complexity can reach O(N^3).
Space
O(N^2), where N is the length of the string. The recursion depth can go up to O(N), and each call might create substrings, leading to a total space usage of O(N^2).
Trade-offs
Pros
Intuitive and directly follows the problem definition.
Relatively easy to understand and implement.
Cons
Inefficient due to repeated computations and string manipulations.
Higher time and space complexity compared to other methods.
Solutions
Solution
class Solution { public int scoreOfParentheses ( String s ) { int ans = 0 , d = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { if ( s . charAt ( i ) == '(' ) { ++ d ; } else { -- d ; if ( s . charAt ( i - 1 ) == '(' ) { ans += 1 << d ; } } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.