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.
This approach processes the string linearly and uses a stack to manage the scores of nested parentheses structures. The stack holds the scores of parenthetical groups at the current level of nesting.
Algorithm
- Initialize a stack of integers and a variable
currentScore = 0. - Iterate through each character
cof the strings. - If
cis(, push thecurrentScoreonto the stack and resetcurrentScoreto 0. - If
cis), pop the score of the enclosing scope from the stack. Let this belastScore. The score of the just-closed group ismax(2 * currentScore, 1). UpdatecurrentScoreto belastScore + max(2 * currentScore, 1). - After the loop,
currentScorewill hold the final total score.
Walkthrough
We can think of the problem as evaluating an expression. An opening parenthesis ( starts a new "scope" or level of calculation, and a closing parenthesis ) concludes the current scope's calculation and merges its result with the parent scope. We use a stack to keep track of the scores of previous, unfinished scopes. We also maintain a currentScore for the current level. When we encounter an (, we are entering a deeper level of nesting. We push the currentScore of the outer level onto the stack and reset currentScore to 0 for the new inner level. When we encounter a ), it signifies the end of the current level. The value of the just-closed group is either 1 (for an empty ()) or 2 * currentScore (for a non-empty (A)). This value is then added to the score of the parent level, which we retrieve by popping from the stack.
import java.util.Stack; class Solution { public int scoreOfParentheses(String s) { Stack<Integer> stack = new Stack<>(); int currentScore = 0; for (char c : s.toCharArray()) { if (c == '(') { stack.push(currentScore); currentScore = 0; } else { int lastScore = stack.pop(); currentScore = lastScore + Math.max(2 * currentScore, 1); } } return currentScore; }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once, and each character involves a constant number of stack operations.
Space
O(N) in the worst case. The size of the stack is determined by the maximum depth of nested parentheses, which can be up to `N/2` for a string like `((...))`.
Trade-offs
Pros
Much more efficient than the recursive approach.
Linear time complexity is optimal for reading the input.
Cons
Requires extra space for the stack, which can be proportional to the input size.
This is the most optimal approach, achieving linear time with constant extra space. It works by observing that the total score is the sum of scores of all the primitive () pairs, where the score of each pair depends on its depth inside the string.
Algorithm
- Initialize
score = 0anddepth = 0. - Iterate through the string
sfromi = 0tos.length() - 1. - If
s[i]is(, incrementdepth. - If
s[i]is), decrementdepth. - If
s[i]is)and the previous characters[i-1]was(, this forms a core()unit. Add1 << depth(which is2^depth) to thescore. - After iterating through the entire string,
scorewill hold the final result.
Walkthrough
The final score can be seen as a sum of powers of 2. Each () pair in the string contributes to the total score. A () pair at a nesting depth d (i.e., enclosed by d pairs of parentheses) contributes 2^d to the final score. For example, in (()(())), the first () is at depth 1, contributing 2^1 = 2. The second () is at depth 2, contributing 2^2 = 4. The total score is 2 + 4 = 6. We can iterate through the string, keeping track of the current depth. When we encounter a () pair (i.e., s[i] == ')' and s[i-1] == '('), we add 2^depth to our total score. The depth here is the number of unmatched ( parentheses enclosing the current () pair.
class Solution { public int scoreOfParentheses(String s) { int score = 0; int depth = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { depth++; } else { depth--; if (s.charAt(i - 1) == '(') { score += 1 << depth; // 2^depth } } } return score; }}Complexity
Time
O(N), as we perform a single pass through the string.
Space
O(1), as we only use a few variables to store the score and depth, regardless of the input string size.
Trade-offs
Pros
Optimal time and space complexity.
Very efficient and concise.
Cons
The logic is less intuitive than the stack-based or recursive approaches and relies on a mathematical insight into the problem structure.
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 ; } }class Solution { public: int scoreOfParentheses ( string s ) { int ans = 0 , d = 0 ; for ( int i = 0 ; i < s . size (); ++ i ) { if ( s [ i ] == '(' ) { ++ d ; } else { -- d ; if ( s [ i - 1 ] == '(' ) { ans += 1 << d ; } } } return ans ; } };class Solution : def scoreOfParentheses ( self , s : str ) -> int : ans = d = 0 for i , c in enumerate ( s ): if c == '(' : d += 1 else : d -= 1 if s [ i - 1 ] == '(' : ans += 1 << d return ansVideo 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.