3 ms·
I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined). Does this technique catch letters
by n4r9 4y ago
I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined).
Does this technique catch letters duplicated more than once?
In a Python 3 shell:
>> 2 ^ 4
6
>> 2 ^ 4 ^ 2
4
>> 2 ^ 4 ^ 2 ^ 2
6
Yes I guess it does, because inputs are used up in order to turn bits on and off. Nice!
- Robin_Message 4y agoThe insight is that the only way to get W bits set is for the last W letters to all have been unique. Duplicate letters toggle bits on and off, but never get you any extra 1 bits set. If you wanted to detect V unique characters from a window of W characters where V < W, this trick wouldn't work. But you could still have a rolling window, it would just be a map counting "how many of this character in the window", which you can increment the relevant character for as it enters the window, and decrement as it leaves.
- mkeeter 4y ago> I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined). Good catch; this should be fixed (using N for input length and W for window size consistently in the writeup).