The hash _solution_ is O(n + m) in that it requires iterating through the words read from the dictionary file (O(m)) to fill the hash and then iterating through the inputs (O(n)), each time doing an O(1) hash lookup. You can think of it as: you need to read each word from the dictionary file once and you need to check each input word once; kind of hard to go faster than that.

Yes, I thought about exactly the same way you explained. But my point is trying to save more time, which may or may not be necessary depending on the size of the input data set. If we use caching, we can save the trip to look up the hashmap for each duplicated word of the input.

However according to the Big O, linear increase does not count. So the Big O is anyway O(n) when n is near m, it's O(2n) then it's O(n), or n >> m or n << m, it is O(n) or O(m). But runtime, there might be some difference. Again, in most of the normal applications using relational database, we will not use huge memory to store extremely large hashmap. We'll put a cap of the size. Indexing unstructured data is a different story.

>save the trip to look up the hashmap for each duplicated word of the input.

The time required to do a hashmap lookup should be small and of constant time. If you did cache it somehow, you would need a way to do lookups of what was cached (which might require another hashmap lookup.)

Edit: I'm saying that trying to cache hashmap lookups might not save you any time and is probably not worth thinking about. Another poster has indicated that the solution described above (without trying to do some kind of caching of duplicates) should be sufficient to pass the Stripe CTF stage, so I would recommend just implementing that.

Good point. It really depends on the size of the data set.

If the size of the input data set m << dictionary data size n, it's a worth trying for caching.

Otherwise, the input word list should be loaded into LinkedList instead of ArrayList which is the most expensive list to be used when we need to access by its index number. Using Set will lose its order.

(I'm just brainstorming the steps for discussion instead of writing code. I'd like to know the best solution and steps to improve it from you guys.)