Count how many times each index is a window edge
Updated
In one standard scan, R takes each index exactly once (each i is the right edge when it enters). L takes each dropped index once as it leaves. Those are the edge events.
What to focus on
An index can sit as the live L for several R values. Count either events (enter/leave) or occupancy. For amortized O(n), count enter-as-R once and leave-as-L at most once.
Worked examples
enter as R
a = [4, 1, 9, 1], R = 0..3- i=0 right edge once
- i=1 once
- i=2 once
- i=3 once
Result: each index is R exactly 1 time
leave as L
s = "abca", unique scan- L starts 0
- at R=3 shrink, index 0 leaves once
- 1,2,3 may still be inside at the end
Result: index 0 is L-leave 1 time
zeros scan
a = [1, 0, 0, 1, 9], k=1- R events: five, one per index
- L leaves index 0 then 1 when zeros hit 2
Result: 5 enters, 2 leaves before the last window
Try it
Write edgeCounts(a). a is an array of integers, or s is a string. R is the right index and takes each i once. L is the left index and leaves an index at most once. Print how many times each i is R and how many times it is dropped as L. Return nothing. For [4, 1, 9, 1], "abca" unique, and [1, 0, 0, 1, 9] k=1.
a (or s) is nonempty. The scan is one forward pass. L and R never reset.