I was playing the Letterpress iPhone App the other day, and I thought about how people would cheat in this game. (You do not ned to know the mechanics of Letterpress to understand this problem.)
Basically you want to form long words given 25 letters. A naive approach to obtain a long word you can form in the game, would be to go through a list of words, then check each word if it can be made from those 25 letters. This is O(N * 25).
However, I thought of a slightly more complex version of the problem, which I was not able to solve:
What if you are given Q queries of 25 letters, and you want to know which words can be formed from those letters, without traversing the word list for each query? Is it possible to run each query in O(log(n)) time, if the word list is stored in some clever data structure?
Can we use one letter multiple times? Can one letter occur twice in our queries? If answer to the second question is 'no', then we have only 26 different queries and the problems becomes very simple.
Did you mean 2^26 different queries?
No, if query is 25 different letters, but it isn't
Ah, I totally missed that there are exactly 25 letters in the queries.
This is actually an alphabet-size-dimensional range query problem, which is not solvable within plain logarithmic time as far as I know. But one can possibly exploit the fact that "coordinates" of words in dictionary are very low positive integers.