4 ms·

I think he meant to use a hash map plus a numOfOnes counter instead of hash set. With a hash map, you don't need to build the entire window every loop. It's onl

I think he meant to use a hash map plus a numOfOnes counter instead of hash set. With a hash map, you don't need to build the entire window every loop. It's only a constant amount of work per iteration, achieving O(N)

DannyBee 4y ago
Yes. You can slide a hash map and a counter, as we went through below. You can also replace the hash map with a bitmask to store the set. 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 ;)
- mateo411 4y ago
  I think you can use a queue of size w. 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 False
  - 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 ago
      Yes, 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.

DannyBee 4y ago

Yes. You can slide a hash map and a counter, as we went through below. You can also replace the hash map with a bitmask to store the set. 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 ;)

mateo411 4y ago
I think you can use a queue of size w. 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 False
- 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 ago
    Yes, 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.