4 ms·
Instead of a queue, you could just use two indices/pointers to the start and end of the current window. Also I think on `char in hash_set` you'd want to advanc
by krackers 4y ago
Instead of a queue, you could just use two indices/pointers to the start and end of the current window.
Also I think on `char in hash_set` you'd want to advance the start of the window until uniqueness is restored, rather than moving start to the end.
E.g. if the string is "abac", when you get to the second "a", instead of restarting the window at the second "a" you want to instead move the start to "b". You might even be able to do something boyer-moore-esque if the hashset is instead a hashmap of chars to index. Then you can directly advance your window by how far in the mismatch is, which probably won't affect asymptotic complexity since you still need to remove elements but allows you to do it in bulk rather than one at a time.
- mateo411 4y agoYes, you are right about advancing the start of the window until uniqueness is restored. So, basically just advance it by 1. You could definitely use two indexes instead of a queue, and using indexes over an array will be faster than using a queue.