This is a problem from Skiena's excellent book The Algorithm Design Manual:
Give an algorithm for finding an ordered word pair(e.g."New York") occurring with the greatest frequency in a given webpage. Which data structure would you use? Optimize both time and space.
We need to look at all the words, so clearly we can't do better than
O(n) time. One solution I can think of is inserting each ordered pair in a priority queue (
O(n) time and space), and then returning the top item. However, the official site has a solution which suggests using a Trie. I understand that words may be repeated, or may be prefix/suffix of other words, so a Trie would save space, but can't figure out how to answer the question using it.