Maintain distinct count in the window06.03
Distinct is the number of keys with count > 0. Increment distinct when a count goes 0→1. Decrement when a count goes 1→0.
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
Same skill, three traces. Read all three before you try it.
01repeats stay 2 - given
a = [1, 2, 1, 3],L=0- walk
R=0distinct1R=1distinct2R=2second1, still2- result
- distinct
2on[0,2]
02new value - given
a = [1, 2, 1, 3],L=0R=2, distinct2- walk
R=3add3,0→1distinct
3- result
- distinct
3on[0,3]
03drop last copy - given
s = "abca",L=0R=3, distinct3- walk
drop
s[0]='a'leavesa:1still
3then drop
s[1]='b'→b:0, distinct2- result
- distinct
2on[2,3]
Write
Print distinct after each expand or shrink.
On
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".constraintsa (or s) is nonempty. Start with a real window [L, R].
- Longest Substring Without Repeating Characters0/3 skills ready · sliding window · mediumopen
- Longest Substring Without Repeating Characters0/3 skills ready · sliding window · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.