Score of Parentheses — Solution in Python, Java & C++
Score of Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Score of Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Stack
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a balanced parentheses string s, compute its score under these rules:
"()"scores1;ABscoresA + B, whereAandBare balanced strings;(A)scores2 * A.
Example 1
Input: s = "()"
Output: 1
Example 2
Input: s = "(())"
Output: 2
Example 3
Input: s = "()()"
Output: 2
Constraints
2 <= s.length <= 30s is a balanced parentheses string.The answer fits in a signed 32-bit integer.
Hints for Score of Parentheses
Hint 1
Keep a stack of partial scores, one frame per open bracket, plus one frame for the whole string.
Hint 2
On
(, push a new frame holding 0.Hint 3
On
), pop the frame: a score of 0 means it was a bare()worth 1, otherwise it is worth double. Add that into the frame below.
How to solve Score of Parentheses
Keep a stack of partial scores, one frame per open bracket; on ), pop the frame and add 1 (if it was empty) or 2 · inner to the frame below.
Approach
- Start
stack = [0]. - On
(, push 0; on), popinnerand add1 if inner == 0 else 2 · innerto the new top. - Return
stack[0].
Why it works
Each frame accumulates the A + B sum of its siblings; closing a frame applies the (A) doubling rule, with the base case () scoring 1.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The O(1)-space trick counts each
()as2^depthwhere depth is the number of enclosing brackets.
Reference solution
Python
def scoreOfParentheses(s: str) -> int:
stack = [0]
for ch in s:
if ch == "(":
stack.append(0)
else:
inner = stack.pop()
stack[-1] += 1 if inner == 0 else 2 * inner
return stack[0]Java
public static int scoreOfParentheses(String s) {
List<Integer> stack = new ArrayList<>();
stack.add(0);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.add(0);
} else {
int inner = stack.remove(stack.size() - 1);
int value = inner == 0 ? 1 : 2 * inner;
stack.set(stack.size() - 1, stack.get(stack.size() - 1) + value);
}
}
return stack.get(0);
}C++
int scoreOfParentheses(string s) {
vector<int> stack;
stack.push_back(0);
for (char c : s) {
if (c == '(') {
stack.push_back(0);
} else {
int inner = stack.back();
stack.pop_back();
stack.back() += (inner == 0 ? 1 : 2 * inner);
}
}
return stack[0];
}JavaScript
var scoreOfParentheses = function(s) {
const stack = [0];
for (let i = 0; i < s.length; i++) {
if (s.charAt(i) === "(") {
stack.push(0);
} else {
const inner = stack.pop();
const value = inner === 0 ? 1 : 2 * inner;
stack[stack.length - 1] += value;
}
}
return stack[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure