Am curious to see having the dictionary in a trie allows you to build an implementation that is O(n). Will add it to the blog post if it works.