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. We can precalculate this value for each pair of words s_i, s_j in a short time.

Now, suppose we have chosen our K words s₁, s₂, ..., s_K. In which order do we print them in order to use a minimum amount of operations? We claim that in fact, if we print the strings in lexicographical order, we will use the minimum amount of operations. Suppose not, let s₁, s₂, ..., s_K be arranged in lexicographical order. Suppose we print the words in the sequence s₁, s₂, ..., s_i - 1, s_j, s_i + 1, ..., s_j - 1, s_i, s_j + 1, ..., s_K, with i < j. Let a₁, a₂, ..., _K be the length of word s₁, s₂, ..., s_K respectively and denote the length of the Longest Common Prefix of s_a and s_b by L(a, b). Then, it can be easily seen that the total number of operations used is 2(a₁ + a₂ + ... + a_K) - 2(L(1, 2) + L(2, 3) + ... + L(i - 1, j) + L(j, i + 1) + ... + L(j - 1, i) + L(i, j + 1) + ... + L(K - 1, K)). Compare this to when the words are printed in lexicographical order. Firstly, if j > i + 1, we just need to compare L(i - 1, j) + L(j, i + 1) + L(j - 1, i) + L(i, j + 1) and L(i - 1, i) + L(i, i + 1) + L(j - 1, j) + L(j, j + 1). We want the former to be at most the latter.