The go-to data structure for this problem is a trie. As each word comes in, we add it to the trie in ~\mathcal O(L)~ time, where ~L~ is the length of the word. In the same amount of time, we can determine what the shortest unique prefix is. If we traverse the trie all the way to the end of a word ~W~, then some word ~W'~ must already exist that has ~W~ as a prefix. In this case, we must type all of ~W~. However, if we hit a leaf node in the trie, then we know that the prefix we'll type is one letter longer than the word stored in that leaf node.