Counting words and prefixes

Write a trie that stores words with repeats, and counts them. insert(word) adds one copy of a word. count(word) returns how many copies of the word are stored. count_prefix(prefix) returns how many stored words start with the prefix, counting every copy. remove(word) removes one copy and returns True; if no copy is stored it changes nothing and returns False.

t = CountingTrie()
t.insert("apple"); t.insert("apple"); t.insert("app")
t.count("apple")         # 2
t.count_prefix("ap")     # 3
t.remove("apple")        # True
t.count_prefix("ap")     # 2
t.remove("ap")           # False: ap was never inserted

Words and prefixes are non-empty and use the letters a to z.

Limits

• Up to 20,000 inserts, 10,000 removes and 25,000 counts, words of at most 6 letters. Every operation should take O(L) time: count_prefix must not visit the words below the prefix one by one.