hackercupai/hackercup huggingface dataset:
The definition of a perfectly balanced string can be simplified to "any even-length string where the character frequencies in the first half are the same as the second half."

Since there are only \(26\) letters, we can precompute a prefix-sum array \(P_c\) of frequencies for each letter \(c\), where \(P_c[i]\) stores the frequency of letter \(c\) in \(S_{1..i}\). This will let us obtain the frequency of any letter \(c\) in any substring \(S_{a..b}\) in constant time, using \(P_c[b] - P_c[a-1]\).

For each query substring \(S_{l..r}\), there are two possible split-points to check in the middle. Let \(m = \lfloor(l + r)/2\rfloor\). We can first compare the frequencies of \(S_{l..(m-1)}\) with \(S_{m..r}\), then compare the frequencies of \(S_{l..m}\) with \(S_{(m+1)..r}\). If in either comparison we find that the frequencies differ by exactly \(1\) letter between the two sides, then \(S_{l..r}\) is almost perfectly balanced.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=w65VekVkuHA)