Alphabet size bounds the window counts
Updated
If every s[i] is from an alphabet of size Σ, the count table has at most Σ live keys. Lowercase English: int[26], distinct ≤ 26, extra space O(1) in Σ.
What to focus on
A hashmap is still correct, but size cannot exceed Σ. A huge n with only a,b,c still has three keys. Do not allocate by n for a 26-letter window.
Worked examples
26 slots
s = "abca"- 'a'-'a'=0, 'b'=1, 'c'=2
- cnt[26] with three nonzeros
- n=4, Σ=26
Result: table length 26, not 4
repeats reuse keys
s = "abcabcbb"- only a,b,c ever appear
- map.size ≤ 3 entire scan
Result: distinct ≤ 3 ≤ 26
k distinct cap
s = "abca", k=2- live keys in a valid window ≤ 2
- never more than Σ either
Result: min(k, Σ) bounds the map
Try it
Write countSlots(s). s is a nonempty lowercase string. Σ = 26 for English letters. The window counts live in cnt[26], not an n-length table. Return how many non-zero slots cnt[26] uses on "abca" and "abcabcbb". Table length is 26, not n. Distinct ≤ 3 on "abcabcbb".
s is a nonempty lowercase string. Σ = 26 for English letters.