Words should be seen as multisets of runes.
Iterate a first time on dictionary to build the multi sets. At the same time keep track off how many words contain 3 "a" and more and how many words contain 1 "e" and more. We should notice that containing 4 z is very rare.
Then build an array from longest word to smallest word that we will fullscan at each query. This should be an array of small structs to avoid cache misses. In the small strict put the word , a pointer to the multi set and an array of the N rarest features of this word. The objective is to discard it as fast as possible without iterating through the whole multiset.