712. The Shortest Stretch Worth Rewriting
A string of length n uses only the letters Q, W, E and R, and n is a multiple of 4.
The string is BALANCED when each letter appears exactly n / 4 times.
You may replace ONE contiguous stretch with any string of the same length. Print the shortest
stretch that makes balancing possible, or 0 if the string is already balanced.
QWER -> 0
QQWE -> 1
QQQW -> 2
WWEQERQWQWWRWWERQWEQ -> 4
## The stretch can be rewritten freely, so only the OUTSIDE matters
Whatever is inside the chosen stretch can be replaced by anything, so it imposes no constraint
at all. The string can be balanced exactly when everything OUTSIDE the stretch has each letter
appearing at most n / 4 times: the freed positions can then be filled to make up the
shortfall, and the counts work out because the lengths match.
So the question becomes: find the SHORTEST window whose removal leaves every outside count at
or below n / 4.
Realising that the window's own contents are irrelevant, and that the constraint lives entirely outside it, is the whole problem. It is the same inversion as 694, 701 and 710, but here it is the short window rather than the long one that is wanted.
## The sweep, shrinking while still legal
for hi in 0 .. n-1:
count[s[hi]] += 1
while lo <= hi and every outside count <= need:
best = min(best, hi - lo + 1)
count[s[lo]] -= 1; lo += 1
where the outside count of letter x is total[x] - count[x].
Note the shape: record INSIDE the shrink loop, before each removal. A shortest-window sweep records while the window is still legal, which is the opposite of problem 703 and matches problem 681.
## Why growing can only help
Widening the window removes more letters from the outside, so outside counts only fall. The condition therefore switches from false to true once and never back, which is exactly the monotonicity a window needs.
## Boundaries
An already balanced string answers 0, and the sweep would otherwise report 1, so the check comes first.
A string of one repeated letter, like QQQQ, needs n - n/4 rewritten, so QQQQ answers 3.
## Cost
Time O(n). Space O(1).
Constraints - `4 ≤ length ≤ 200000` - the length is a multiple of 4 - every character is `Q`, `W`, `E` or `R`
Input
One line containing the string, whose length is a multiple of 4.
Output
Print one integer, the length of the shortest stretch to rewrite.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.