Score of parentheses requires inspecting every character in input
Many Scores Force Many Reads: An Optimality Proof for Score of Parentheses
Data Structures and Algorithms
Summary
Calculating the score of a balanced parentheses string is a known problem that can be solved quickly with little memory. The authors prove that any algorithm must read every character at least once to compute the score correctly, showing it can’t be done faster. They demonstrate this by creating many different balanced strings that all need to be distinguished to get the right score, proving a linear time lower bound. This confirms that existing fast methods are as efficient as possible.
What this means in practice
- •For software developers: Design parsers or interpreters recognizing balanced parentheses, knowing no algorithm can run in less than linear time.
- •For compiler engineers: Optimize code for parentheses scoring by accepting the proven linear read requirement and minimizing constant factors.
A theory result. No direct application yet.
Authors
Andrew Au
Abstract
LeetCode Problem 856, Score of Parentheses, admits a one-pass algorithm using $O(n)$ time and $O(1)$ auxiliary registers. Its correctness follows from a local interpretation: every occurrence of () contributes a power of two determined by its nesting depth. The space bound is immediately optimal in the usual programming-challenge model, but the linear-time bound is less obvious. In particular, a direct adversary that forces an algorithm to inspect every character is difficult to maintain under the promise that the input is balanced. We instead prove a counting lower bound. For every $k$, we construct $2^k$ balanced parenthesis strings of the same length $4k+2$, all having distinct scores. The construction encodes each bit using one of two operations, changing a current score $v$ to either $2v+1$ or $2v+2$. Consequently, any deterministic character-query decision tree computing the score must have depth at least $k$. A two-character padding argument extends the result to every even input length, proving an $Ω(n)$ worst-case time lower bound. The one-pass algorithm is therefore asymptotically optimal in the unit-cost RAM model.