Maintain distinct count in the window
Updated
Distinct is the number of keys with count > 0. Increment distinct when a count goes 0→1. Decrement when a count goes 1→0.
What to focus on
A repeat does not change distinct. Deleting the last copy does. After every move, distinct equals how many different values sit in [L,R].
Worked examples
repeats stay 2
a = [1, 2, 1, 3], L=0- R=0 distinct 1
- R=1 distinct 2
- R=2 second 1, still 2
Result: distinct 2 on [0,2]
new value
a = [1, 2, 1, 3], L=0 R=2, distinct 2- R=3 add 3, 0→1
- distinct 3
Result: distinct 3 on [0,3]
drop last copy
s = "abca", L=0 R=3, distinct 3- drop s[0]='a' leaves a:1
- still 3
- then drop s[1]='b' → b:0, distinct 2
Result: distinct 2 on [2,3]
Try it
Write windowDistinct(a). a is an array of integers, or s is a string. L is the left index. R is the right index. The window includes a[L..R]. Distinct is how many values have count > 0. Print distinct after each expand or shrink. A 0-count key must not inflate it. Return nothing. On [1, 2, 1, 3] and "abca".
a (or s) is nonempty. Start with a real window [L, R].