Score of Parentheses
Problem Description
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
Input: s = "()"
Output: 1
Input: s = "(())"
Output: 2
Input: s = "()()"
Output: 2
Constraints
- 2 <= s.length <= 50
- s consists of only '(' and ')'.
- s is a balanced parentheses string.
Solving the given problem statement involves critical thinking and pen and paper work rather than the Brute Force Approach, we need to take examples and figure out the working algorithm, let's see how we can figure out the approach !!.
Optimal Approach
Intuition
Before moving forward with the question, let's first note down few observations from the given example and then proceed with the approach.
When our input string is "()", the score will be 1. This represents the basic unit of a balanced pair of parentheses.
For an input string like "()()", the score will be 1+1=2, as each balanced pair of parentheses contributes a score of 1 independently.
Finally, for a string like "(())", the score will be 2×1=2. This is because the parentheses are nested, and the score of the inner balanced pair is doubled due to the nesting.
These given examples can be the base of our algorithm,let's take another example
suppose s="( ( ( ) ) ) ( )"
Output:- 5
From the above image, we can observe that we are obtaining the values from the most nested parentheses and then pass on the values as we come to the outer ones.
We got our first observation,
when we see a nested parentheses, we will multiply it by 2.
Nested Parentheses?? Have we read it earlier on how to know the depth of parentheses aka number of nested parentheses?
We are getting intuitions of using a stack
In the example we took i.e s= " ( ( ( ) ) ) ( ) "
Whenever, we encounter the '(' at index 0, we can say that we are moving 1 layer deeper, this means that we will be getting a value of 1,2,3,...
Why we say that the score will be 1 when we encounter a '(' ?
Because we are given a valid parentheses, so for every '(' there will be a ')' and we know that "()" has a value 1 and so on if we have more no of valid parentheses inside it.
We still need to figure out the algorithm, let's take a scenario.
Imagine we have a bunch of boxes, and some of them are inside other boxes. Each box has either a small toy inside or another box. How can we figure out the total number of toys.
Every time we open a new box
we either encounter another box or a toy, when we see a open box i.e. a '(', we put a note on the table saying, "Remember how many toys we counted so far," and we reset our count to zero because we're going to count the toys in this new box.
When, we close a box i.e. when we see a ')', we check how many toys we found in that box. If there were smaller boxes inside, we count their toys (we figured out it earlier) when they're in a smaller box. Then, we add this number to the count we wrote on the note. When we're done opening and closing all the boxes, we look at our final count to see how many toys we have in total.
Programmatically, we will maintain a stack to store the score as we traverse the string.
When we encounter a '(' (we open a box ), we will add a score 0 to the stack. When we encounter a ')' (We close a box), we will evaluate the score which is nothing but 2*(no of nested parentheses present inside it) + top of stack (previous scores that are pushed).
So, the formula we use is:-
score = stack.pop() + Math.max(2 * score, 1);
Why "score = stack.pop() + Math.max(2 * score, 1)" ?
st.pop(): When we encounter a closing parenthesis ), it means we're finishing a group of parentheses. The st.pop() retrieves the score of the outer group (from the stack) that we saved earlier.
This ensures that we can add the score of the current group to the outer one correctly.
Math.max(2 * score, 1): This calculates the score for the current group of parentheses. If the score inside the parentheses (score) is 0, it means the parentheses are simply (). In this case, the score is 1 (the base case).
If the score is greater than 0, it means we have nested parentheses like (()). The score of the nested group is doubled (i.e., 2 * score).
st.pop() + ...: The result of Math.max(2 * score, 1) is added to the popped value from the stack (st.pop()). This step combines the score of the current group with the score of the outer group that was saved on the stack.
Let's see how to code it up !!
Approach
Initialize a stack to store intermediate scores. Set the initial score to 0.
Iterate through each character in the input string:
- If the character is an opening parenthesis '(': Push the current score onto the stack. Reset the score to 0 to start calculating for the new group.
- Else (the character is a closing parenthesis ')'):
Pop the top value from the stack (representing the outer score).
Update the score as the popped value plus the maximum of: Twice the current score (if there's a nested group), or 1 (if it's a simple ()).
Return the final score after processing the entire string.
Dry-Run
Input s="( ( ( ) ) ) ( )"
Output:- 5
First Character: '('
- Push score (0) onto the stack.
- Reset score to 0.
- Stack: [0]
- Score: 0
Second Character: '('
- Push score (0) onto the stack.
- Reset score to 0.
- Stack: [0, 0]
- Score: 0
Third Character: '('
- Push score (0) onto the stack.
- Reset score to 0.
- Stack: [0, 0, 0]
- Score: 0
Fourth Character: ')'
- Pop the top value from the stack (0).
- Update score = popped value + max(2 * score, 1) → score = 0 + max(2 * 0, 1) → score = 1.
- Stack: [0, 0]
- Score: 1
Fifth Character: ')'
- Pop the top value from the stack (0).
- Update score = popped value + max(2 * score, 1) → score = 0 + max(2 * 1, 1) → score = 2.
- Stack: [0]
- Score: 2
Sixth Character: ')'
- Pop the top value from the stack (0).
- Update score = popped value + max(2 * score, 1) → score = 0 + max(2 * 2, 1) → score = 4.
- Stack: []
- Score: 4
Seventh Character: '('
- Push score (4) onto the stack.
- Reset score to 0.
- Stack: [4]
- Score: 0
Eighth Character: ')'
- Pop the top value from the stack (4).
- Update score = popped value + max(2 * score, 1) → score = 4 + max(2 * 0, 1) → score = 5.
- Stack: []
- Score: 5
Final State: Score: 5
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
// Function to calculate the score of parentheses
int scoreOfParentheses(string s) {
// Initialize a stack to store intermediate scores
stack<int> st;
// Initialize the current score to 0
int score = 0;
// Loop through each character in the string
for (char ch : s) {
// If the character is an opening parenthesis '('
if (ch == '(') {
// Push the current score onto the stack
st.push(score);
// Reset the score to 0 for the new group
score = 0;
}
// If the character is a closing parenthesis ')'
else {
// Pop the top value from the stack (outer score)
score = st.top() + max(2 * score, 1);
st.pop();
}
}
// Return the final score
return score;
}
};
2. Java Try on Compiler
class Solution {
// Function to calculate the score of parentheses
public int scoreOfParentheses(String s) {
// Initialize a stack to store intermediate scores
Stack<Integer> stack = new Stack<>();
// Initialize the current score to 0
int score = 0;
// Loop through each character in the string
for (int i = 0; i < s.length(); i++) {
// Get the current character
char ch = s.charAt(i);
// If the character is an opening parenthesis '('
if (ch == '(') {
// Push the current score onto the stack
stack.push(score);
// Reset the score to 0 for the new group
score = 0;
}
// If the character is a closing parenthesis ')'
else {
// Pop the top value from the stack (outer score)
score = stack.pop() + Math.max(2 * score, 1);
}
}
// Return the final score
return score;
}
}
3. Python Try on Compiler
# Function to calculate the score of parentheses
def score_of_parentheses(s):
# Initialize a stack to store intermediate scores
stack = []
# Initialize the current score to 0
score = 0
# Loop through each character in the string
for ch in s:
# If the character is an opening parenthesis '('
if ch == '(':
# Push the current score onto the stack
stack.append(score)
# Reset the score to 0 for the new group
score = 0
# If the character is a closing parenthesis ')'
else:
# Pop the top value from the stack (outer score)
score = stack.pop() + max(2 * score, 1)
# Return the final score
return score4. JavaScript Try on Compiler
// Function to calculate the score of parentheses
function scoreOfParentheses(s) {
// Initialize a stack to store intermediate scores
let stack = [];
// Initialize the current score to 0
let score = 0;
// Loop through each character in the string
for (let ch of s) {
// If the character is an opening parenthesis '('
if (ch === '(') {
// Push the current score onto the stack
stack.push(score);
// Reset the score to 0 for the new group
score = 0;
}
// If the character is a closing parenthesis ')'
else {
// Pop the top value from the stack (outer score)
score = stack.pop() + Math.max(2 * score, 1);
}
}
// Return the final score
return score;
}
Time Complexity: O(n)
The algorithm processes the string exactly once, iterating through each character.
For each character: Pushing onto the stack (stack.push) and popping from the stack (stack.pop) are O(1) operations. Calculating Math.max or equivalent operations are also O(1).
Thus, the time complexity of the algorithm is: O(n)
Space Complexity: O(d)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
The stack is used to store intermediate scores. The size of the stack depends on the maximum depth of the nested parentheses in the input string. In the worst case, when the string contains only nested parentheses (e.g., "((((((((()))))))))"), the stack will hold at most n/2 elements (as each '(' requires a push, and each ')' requires a pop).
Thus, the auxiliary space complexity is: O(d)
Total Space Complexity
The total space complexity includes both:
- Auxiliary space used by the stack: O(d).
- Input storage: The string itself requires O(n). space.
Thus, the total space complexity is: O(n+d)=O(n)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
- For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.
A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.
Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.
A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:
- It is the empty string, or
- It can be written as AB (A concatenated with B), where A and B are VPS's, or
- It can be written as (A), where A is a VPS.
We can similarly define the nesting depth depth(S) of any VPS S as follows:
- depth("") = 0
- depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
- depth("(" + A + ")") = 1 + depth(A), where A is a VPS.
For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.
Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).
Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.
Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.