856. Score of Parentheses
Problem Description
The problem presents us with a string s
that contains only balanced parentheses. A balanced parentheses string means every opening parenthesis '(' has a corresponding closing parenthesis ')'. Our goal is to compute the "score" of this string based on certain rules:
- A pair of parentheses "()" directly next to each other has a score of 1.
- The score
AB
for two consecutive balanced parentheses stringsA
andB
is the sum of their individual scores, i.e.,score(A) + score(B)
. - The score
(A)
for a balanced parentheses stringA
enclosed within another pair of parentheses is double the score ofA
, i.e.,2 * score(A)
.
The problem asks us to compute the total score of the given string based on these rules.
Intuition
To solve this problem, we can iterate through the string while keeping track of two things: the depth of nested parentheses d
, and the current score ans
. The depth increments each time we encounter an opening parenthesis '(' and decrements with a closing parenthesis ')'. The key insight is that a single pair of parentheses "()" contributes score based on the depth of nesting at that point; specifically, it contributes a score of 2^d
, where d
is the depth just before the pair ends.
Here is the thought process to arrive at the solution:
- Initialize the answer variable
ans
to zero and depth variabled
to zero. - Loop through each character
c
in the strings
, using its indexi
to access previous characters if needed. - If we encounter an opening parenthesis '(', we increase the depth
d
by 1, indicating we are going deeper in the nested structure. - If we encounter a closing parenthesis ')', this means we are completing a parenthetical group; so we decrease the depth
d
by 1. - Now, if the closing parenthesis is immediately following an opening one, i.e., we have a pair "()", it's time to add the score.
- The tricky part is that if this pair is nested inside other pairs, its contribution to the score is not merely 1 but is actually
2^d
whered
is the depth just before this pair. - This is because each layer of nesting effectively doubles the score of the pair inside it.
- We efficiently calculate
2^d
as1 << d
because bit shifting to the left is equivalent to multiplying by two. - We then add this computed score to
ans
.
- The tricky part is that if this pair is nested inside other pairs, its contribution to the score is not merely 1 but is actually
- After processing all characters,
ans
holds the final score of the string, which we return.
This way, by using a depth variable and a bit of bitwise arithmetic, we compute the score in a single pass over the input string.
Learn more about Stack patterns.
Solution Approach
The provided solution takes advantage of a stack-like behavior but optimizes it by using a depth variable instead to keep track of the levels of nested parentheses. This means that rather than actually pushing and popping from a stack, we can simply increment and decrement a depth counter to simulate the stack's depth tracking behavior.
Here's a step-by-step walkthrough of the implementation using the Reference Solution Approach:
-
Initialization: We initialize two integer variables:
ans
: To store the cumulative score of the balanced parentheses string.d
: To keep track of the depth of the nested parentheses.
-
Traversal: We iterate through each character
c
of the strings
. The loop utilizesenumerate
to gain both the indexi
and the characterc
. -
Depth Update:
- When we encounter an opening parenthesis '(', we are going deeper into a level of nesting, so we increase
d
by 1. - Conversely, for a closing parenthesis ')', we decrease
d
by 1 as we are coming out of a nested level.
- When we encounter an opening parenthesis '(', we are going deeper into a level of nesting, so we increase
-
Score Calculation:
- The crucial observation for score computation is made when we encounter a closing parenthesis ')'.
- We check if the previous character
(s[i - 1])
was an opening parenthesis '('. If it was, then we have found a "()" pair. - The score of this pair is
1 << d
(which is2
raised to the power ofd
). This is because each additional depth level doubles the score of a pair of parentheses. - We add this score to our answer
ans
.
-
Result: After the loop completes,
ans
holds the total score of the string which is then returned.
Algorithm: The algorithm is effectively a linear scan with a depth counting approach. The algorithm runs in O(n) time, with n being length of the string s
, as each character is visited once.
Data Structures: While a stack is the intuitive choice for dealing with nested structures, this solution optimizes space complexity by using a single integer for depth tracking instead.
Patterns: This is an example of a single-pass algorithm with a small space optimization. The bit shifting trick (1 << d
) is a clever way to compute powers of two that leverages the binary representation of integers.
This approach is efficient both in terms of time and space complexity, performing the calculation in linear time while using constant space.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example string: "(())()"
.
-
Initialization:
ans = 0
: To store the cumulative score.d = 0
: To keep track of the depth of nested parentheses.
-
Traversal:
- We start with the first character '('.
d
becomes1
because we have entered a new level of nesting.
- Next character '(':
d
becomes2
as we go deeper.
- We encounter a closing parenthesis ')':
d
is2
, hence before decreasingd
, we check the previous character which is '('.- Since it forms a pair "()", we add
1 << (d - 1)
toans
which is1 << 1
=2
. ans = ans + 2
andd
decreases to1
.
- The next character is ')' again:
d
is1
, and we check the previous character which is not '(', so we just decreased
by1
.ans
stays the same since we don't have a new pair, andd
decreases to0
.
- Next character '(':
d
becomes1
since we are starting a new nesting level.
- Lastly, we encounter ')':
d
is1
, the previous character is '(', so this is a pair "()", and we add1 << (d - 1)
which is1 << 0
=1
toans
.ans = ans + 1
andans
becomes3
, thend
goes back to0
.
- We start with the first character '('.
-
Traversal Complete:
- We have processed all characters, and our final score
ans
is3
.
- We have processed all characters, and our final score
This example verifies our approach to scoring the string. Each pair of parentheses that forms "()" directly contributes 1 << (depth - 1)
to the score, with the depth being counted just before the closing parenthesis of the pair.
Solution Implementation
1class Solution:
2 def scoreOfParentheses(self, s: str) -> int:
3 # Initialize the score and the current depth of the parentheses.
4 score = current_depth = 0
5
6 # Enumerate over the string to process each character along with its index.
7 for index, char in enumerate(s):
8 if char == '(': # If the character is an opening parenthesis,
9 current_depth += 1 # increase the depth.
10 else: # If it's a closing parenthesis,
11 current_depth -= 1 # decrease the depth.
12 # If the previous character was an opening parenthesis,
13 # it's a pair "()". Add 2^depth to the score.
14 if s[index - 1] == '(':
15 score += 1 << current_depth
16
17 # Return the final computed score.
18 return score
19
1class Solution {
2 public int scoreOfParentheses(String s) {
3 // Initialize score and depth variables
4 int score = 0;
5 int depth = 0;
6
7 // Iterate over the string
8 for (int i = 0; i < s.length(); ++i) {
9 // Check if the current character is an opening parenthesis
10 if (s.charAt(i) == '(') {
11 // Increase depth for an opening parenthesis
12 ++depth;
13 } else {
14 // Decrease depth for a closing parenthesis
15 --depth;
16 // If the current character and the previous one are "()",
17 // it's a balanced pair which should be scored based on the current depth
18 if (s.charAt(i - 1) == '(') {
19 // Score the pair and add it to the total score
20 // 1 << depth is equivalent to 2^depth
21 score += 1 << depth;
22 }
23 }
24 }
25 // Return the final computed score
26 return score;
27 }
28}
29
1class Solution {
2public:
3 int scoreOfParentheses(string S) {
4 // Initialize the score 'score' and the depth of the parentheses 'depth'
5 int score = 0;
6 int depth = 0;
7
8 // Loop through each character in the string
9 for (int i = 0; i < S.size(); ++i) {
10 if (S[i] == '(') {
11 // Increase depth for an opening parenthesis
12 ++depth;
13 } else {
14 // Decrease depth for a closing parenthesis
15 --depth;
16 // Check if the previous character was an opening parenthesis
17 // which represents the score of a balanced pair "()"
18 if (S[i - 1] == '(') {
19 // Add to score: 2^depth, where depth is the
20 // depth of nested pairs inside the current pair
21 score += 1 << depth;
22 }
23 }
24 }
25 // Return the final computed score
26 return score;
27 }
28};
29
1let score: number = 0; // Global score variable
2let depth: number = 0; // Global depth variable to track the depth of parentheses
3
4function scoreOfParentheses(S: string): number {
5 score = 0; // Initialize score
6 depth = 0; // Initialize depth
7
8 // Loop through each character of the string
9 for (let i = 0; i < S.length; i++) {
10 if (S[i] === '(') {
11 // If character is '(', increase the depth as this signifies entering a deeper level of nested parentheses
12 depth++;
13 } else {
14 // If character is ')', decrease the depth as this signifies exiting from the current level
15 depth--;
16
17 // Check if the previous character was '(' to find a '()' pair which contributes to the score
18 if (S[i - 1] === '(') {
19 // The score of a pair is 2 to the power of its depth in the overall structure
20 score += 1 << depth;
21 }
22 }
23 }
24 // Return the computed score after processing the entire string
25 return score;
26}
27
28// The function scoreOfParentheses can now be used without a class, like so:
29// let result = scoreOfParentheses("(()(()))");
30
Time and Space Complexity
Time Complexity
The time complexity of the function scoreOfParentheses
is O(n)
, where n
is the length of the string s
. This is because there is a single loop that iterates through each character of the string s
exactly once.
Space Complexity
The space complexity of the function is O(1)
. The only extra space used is for the variables ans
and d
, which store the cumulative score and the current depth respectively. The space used does not scale with the size of the input string, so the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first