3 ms·
Isn't the memory just O(Unique) since the window size is bounded by the max number of unique characters (in this case 26)? In the general case, the hash would n
by NathanaelRea 4y ago
Isn't the memory just O(Unique) since the window size is bounded by the max number of unique characters (in this case 26)? In the general case, the hash would need to store one bit for each unique element.
If you use a bit mask, you allocate all the memory up front. In a set you allocate through runtime, but could just use set.add(char - 'a') for a similar memory bound. But both need to be able to store every unique element. They are both O(Unique), it just happens that 26 <= num_bits(u32).
- qsort 4y agoYes. It's a neat trick, but from an algorithmic point of view it's exactly the same as the obvious solution, replacing a set with a hash-set. I did this with a counter in python: def first_diff(s, n): cnt = Counter() for i, c in enumerate(s, 1): cnt[c] += 1 if i > n: top = s[i - n - 1] cnt[top] -= 1 if cnt[top] == 0: del cnt[top] if len(cnt) == n: return i