710. Collecting k of Each From the Two Ends
A string uses only the letters a, b and c. Each move removes ONE character from either
end. Print the fewest moves needed to have collected at least k of each letter, or -1 if
it is impossible.
aabaaaacaabc, k = 2 -> 8
abc, k = 1 -> 3
cccbba, k = 1 -> 3
abc, k = 2 -> -1
## Leave the most, take the least
What is removed is a prefix plus a suffix, so what REMAINS is a contiguous middle. Taking the fewest is leaving the longest.
The middle may keep at most total[x] - k copies of each letter x, because everything it
keeps is a copy NOT collected. So:
· find the LONGEST window in which each letter x appears at most total[x] - k times
· the answer is n minus that length
The same inversion opens problem 694, and it is the move that makes a window apply at all.
## The sweep
for hi in 0 .. n-1:
count[s[hi]] += 1
while some letter is over its allowance:
count[s[lo]] -= 1; lo += 1
best = max(best, hi - lo + 1)
Only three letters exist, so the "over its allowance" test is three comparisons, not a scan.
## The impossibility test comes first
If the whole string holds fewer than k of any letter, no sequence of moves can succeed and
the answer is -1. Checking this BEFORE the sweep matters: otherwise an allowance is negative,
no window is ever legal, and the code reports n moves for a case that has no answer at all.
abc with k = 2 is that case, and it is the test worth writing first.
## When the answer is the whole string
abc with k = 1 needs every character, so the longest legal middle has length 0 and the
answer is 3. A window sweep reports 0 correctly here because no non-empty window is legal, so
unlike problem 694 this boundary needs no special handling.
Two problems with the same inversion and different boundary behaviour, for the same reason in each case: 694's target can be met by an empty middle that the sweep cannot represent, while here an empty middle is the sweep's natural answer of 0.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ length ≤ 200000` - `1 ≤ k ≤ 100000` - every character is `a`, `b` or `c`
Input
The first line contains an integer k.
The second line contains the string.
Output
Print one integer, the fewest moves, or -1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.