Medium · Stack & Monotonic Stack · about 15 minutes
Asked at Google, Amazon, Microsoft, Meta.
Score a balanced parentheses string: "()" scores 1, AB scores A + B, and (A) scores 2 * A.
"()"
AB
A + B
(A)
2 * A