If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)
You actually don't need any extra anything at all if you want, as you can just keep a single count because you don't need to look back at old windows, and can keep moving forward to the last non-unique point, making it O(N).
I'm sure this being HN, someone will come along and post how to do this.
I already got caught out once by trying to code it too fast so not gonna do it ;)
Something like this... this is psuedo code. You iterate through the string once. You pop an element off of the queue at most once. In this implementation you might add it to the queue twice.
def find_uniq_window(long_string, w):
queue = Queue()
hash_set = Hashset()
for char in long_string:
if queue.size() == w:
old_char = queue.pop()
hash_set.remove(old_char)
queue.push(char)
if char not in hash_set and queue.size() == w:
# success
return queue
if char in hash_set:
#empty the queue and hash set and start over
queue = Queue()
hash_set = HashSet()
queue.push(char)
hash_set.add(char)
# We never found the window of unique characters, so return false
return FalseAlso 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.
You could definitely use two indexes instead of a queue, and using indexes over an array will be faster than using a queue.