At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural

At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural lower boundary seems to be O(document size + vocabulary size). Also it is unclear what will count as an atomic operation. Although the description reads as if word comparisons were counted, this makes for another simplification, as words could be of arbitrary size. Also: I only checked the HN comment section to see if someone got the solution and I am amazed that others stuck to that part as well.