LeetCode Entry

856. Score of Parentheses

05.10.2026 medium 2026 kotlin rust

Evaluate braces concatenation is sum and wrap is 2

856. Score of Parentheses medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1503

Problem TLDR

Evaluate braces concatenation is sum and wrap is *2

Intuition

• replace braces recursively by finding the innermost
• or use stack and do pop*2+pop
• or use leaf-only sum, each leaf contributes 2^depth

Approach

• the simplest idea is the stack

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun scoreOfParentheses(s: String): Int = ArrayDeque(setOf(0)).apply {
        for (c in s) if (c == '(') add(0) else add(max(1, 2*removeLast()) + removeLast())
    }.last()

    pub fn score_of_parentheses(s: String) -> i32 {
        let (mut d, mut r) = (1, 0);
        for w in s.as_bytes().windows(2) {
            if w[1] == 40 { d += 1 } else { d -= 1; r += ((41 - w[0]) as i32) << d }
        } r
    }