Sliding Window · variable window, sub-variant C — minimise LeetCode 1234

Replace the Substring for Balanced String / visualized

The reframing is the whole problem. You are not hunting for a balanced substring — the window is the part you are allowed to overwrite, and you may write anything you like into it. So the only question is whether what is outside the window can still be balanced, and that is true exactly when every character’s outside count is ≤ n/4. Flip the statistic and the machine is ordinary: r always advances, pulling a character out of the outside tally; while the outside is already balanced the window is valid, so shrink l — which pushes a character back into the tally — and record best inside that loop. Sub-variant C. An input that is already balanced needs no window at all and returns 0.

s — letters Q W E R only, length a multiple of 4

Execution

idle

s · teal is the window you may overwrite — plain cells are the ones being counted

counts outside the window · the tick is the ceiling n/4 = 2

Press Run to begin.

0 / 0

Speed

Java · running line

the window — free to overwrite r enters (count leaves the outside) l exits (count rejoins the outside) a count above n/4 shortest window recorded

O(n) time · O(1) space (four counters) · Sub-variant C: record best inside the shrink loop. The window is the part you overwrite; the invariant lives in its complement. If the string is already balanced the answer is 0, which is why that case is tested before the loop ever starts.