Abridged Problem Statement : You have a list of N distinct words, and you want to print K of them. You have a very basic text editor : It supports 3 types of operations: typing a letter, deleting the previous letter, and printing the current document. You need to leave the document empty after printing K words. What's the minimum number of operations required to get the job done?

Constraints : 1 ≤ K ≤ N ≤ 300 The total length of all N words in each set will be at most 100, 000 characters.

Solution :

Name the words s₁, s₂, ..., s_N. Let s₀ = "". We initially have s₀ on the document. After some operations, we want to print k of s₁, s₂, ..., s_N and change the document to s₀. For some pair of string s_i, s_j, how many operations do we need to print s_j if we have a document with s_i? Let p be the length of the Longest Common Prefix of s_i and s_j. We can compute this naively in O(min(|s_i|, |s_j|)). Then, we need to delete |s_i| - p characters, type |s_j| - p characters, and print it (1 operation), for a total of |s_i| + |s_j| - 2p + 1 operations.