Monocarp's String

Let’s strip away the story. Removing a consecutive block changes the counts only by whatever was inside that block.

Define the value of each character like this:

• 'a' = $+1$
• 'b' = $-1$

For any string or substring, its sum is:

$$\#a - \#b$$

So the string has equal numbers of 'a' and 'b' exactly when its sum is $0$.

What must be removed?

Let the total sum of the original string be $D$.

If we remove some substring with sum $X$, then the remaining string has sum:

$$D - X$$

We want the remaining string to be balanced, so:

$$D - X = 0$$

Therefore:

$$X = D$$

That is the whole problem: find the shortest consecutive substring whose balance equals the total balance of the whole string.

If $D=0$, the string is already balanced, so the answer is $0$. No need to touch anything.

Prefix sums

Let $pref[i]$ be the sum of the first $i$ characters, with $pref[0]=0$.

The sum of substring $l \dots r$ is:

$$pref[r+1] - pref[l]$$

We need:

$$pref[r+1] - pref[l] = D$$

Rearrange it:

$$pref[l] = pref[r+1] - D$$

So while scanning from left to right, suppose the current prefix sum is $cur = pref[i]$. We want some earlier prefix sum equal to $cur - D$.

If such an earlier prefix was at index $j$, then substring $j \dots i-1$ has sum $D$, and its length is:

$$i-j$$

We want the shortest length, so for each prefix sum, we should store the latest index where it appeared. Latest gives the smallest possible $i-j$ for the current ending position. Keeping the earliest would be great for longest subarrays, but here it would be the wrong tool. Classic off-by-one trap wearing a fake mustache.

Why output -1?

The entire string always has sum $D$, so removing all characters always technically works. But the statement says if removing all letters is necessary, output -1.

So after finding the minimum substring length:

• if it is $n$, print -1
• otherwise print that minimum length

This also handles strings like aaaa or aabaa, where no proper substring can fix the imbalance.

Complexity

Each character is processed once. Prefix sums range from $-n$ to $n$, so a hash map is more than enough.

Time complexity per test case: $O(n)$

Memory complexity per test case: $O(n)$