[Java] Minimum number of characters to delete from string to create valid word

Given a string s and a set of words, find the minimum number of characters to delete from the string to generate a valid word.

If no word can be created, return -1.

We use a BFS approach to explore all strings generated by deleting one character from a given string, and track which strings we have generated so far to avoid doing duplicate work.

Each time we generate a new string, we query the set to check whether it's a valid word, and if yes, return the result.

We also notice that from a word of length N, it's impossible to generate any string of length N by removing a character, therefore there is no need to keep a word in our seen set AFTER we have processed it.

With this approach our worst case is where the string is made of all unique characters and no dictionary word can be generated. We have a O(2^N) time as for each character in the string, we either add a new string or not to our exploration space and by tracking the seen nodes using extra O(N) space we avoid a factorial runtime. The space is O(N) since we track only the nodes that are currently in the queue, and because we do not add duplicates, we add at most 2N strings to the queue at any given time.

Another thing to observe is that the substring function cost is O(N), so generating all strings with one less character from a given string of length N is total O(N^2) time. For all nodes at each level we do O(N^2) work to generate all strings for the next level.

The final runtime would be (2^N + N^2) which is O(2^N)

You can check my implementation of minDeletionsToFormDictionaryWord on my Gist along with some tests in MinDeletionsToFormDictionaryWordJTests.