705. Where Every Letter Pulls Its Weight

Find the longest contiguous stretch of a lowercase string in which EVERY letter that appears does so at least k times. Print its length, or 0 if no such stretch exists.

aaabb, k = 3 -> 3 aaa ababbc, k = 2 -> 5 ababb aabbcc, k = 2 -> 6 abcde, k = 2 -> 0

## Why the ordinary window does not work here

A sliding window needs the tested property to move in ONE direction as the window grows. "Every letter appears at least k times" does not: adding a letter can satisfy the condition or break it, depending on which letter arrives.

aabb with k = 2 is legal; adding a c breaks it; adding two more c fixes it again. There is no left edge to shrink to, so the usual sweep has nothing to do.

Recognising that a window does not apply, and then finding the extra constraint that makes it apply, is the real content of this problem.

## Fix the number of distinct letters

There are only 26 letters, so the answer contains between 1 and 26 distinct ones. Ask the question 26 times:

· for d = 1, 2, ..., 26, find the longest stretch with EXACTLY d distinct letters, every one of them appearing at least k times

With d fixed, "at most d distinct" IS monotone, so the window works again. Inside it, keep a second number: how many letters currently reach k. The stretch is valid exactly when that number equals d.

for d in 1 .. 26: lo = 0; uniq = 0; ge = 0; counts = zeros for hi in 0 .. n-1: add s[hi] # uniq += 1 when its count becomes 1; ge += 1 when it reaches k while uniq > d: drop s[lo] # ge -= 1 when its count leaves k; uniq -= 1 when it hits 0 lo += 1 if uniq == d and ge == d: best = max(best, hi - lo + 1)

## The two counters and their exact thresholds

uniq changes when a count crosses 0. ge changes when a count crosses k, so the tests are count == k on entry and count == k BEFORE the decrement on exit. Writing >= k in either place double counts.

## Why 26 passes is not cheating

Each pass is O(n), so the total is O(26n), which is linear in everything that grows. The alphabet is a constant of the problem, not of the input.

## Boundaries

k = 1 accepts the whole string, since every present letter appears at least once. A k larger than the string length answers 0.

## Cost

Time O(26 n). Space O(26).

Constraints - `1 ≤ length ≤ 100000` - `1 ≤ k ≤ 100000` - every character is a lowercase letter