We denote a concatenation of strings by \(\oplus\).

We think that this problem has many false solutions (those which do not yield correct answers), so we will introduce some false solutions and their counterexamples.

---

Sample false solution 1

Sort \((S_1, \ldots,S_N)\) so that \(S_i \leq S_{i+1}\).
The answer is a concatenation of the first \(K\) terms.

The answer for the following case is bab, but it outputs bba.

2 2
b
ba

---

Sample false solution 2

Sort \((S_1, \ldots,S_N)\) so that \(S_i \oplus S_{i+1} \leq S_{i+1}\oplus S_i\).
The answer is a concatenation of the first \(K\) terms.

The answer for the following case is b, but it outputs ba.

2 1
b
ba

---

Sample false solution 3

Sort \((S_1, \ldots,S_N)\) so that \(S_i \oplus S_{i+1} \leq S_{i+1}\oplus S_i\).
Define DP (dynamic programming) by
\(dp[i][j] := \)(the lexicographically smallest string of concatenations of \(j\) strings chosen from \((S_1,\ldots,S_i)\)),
with transition
\(dp[i][j] = \min(dp[i-1][j],dp[i-1][j-1] \oplus S_i)\).
The answer is \(dp[N][K]\).

The answer for the following case is baab, but it outputs baaba.

3 2
baa
ba
b

---

Sample false solution 4

Sort \((S_1, \ldots,S_N)\) so that \(S_i \oplus S_{i+1} \leq S_{i+1}\oplus S_i\).
Define DP by
\(dp[i][j] := \)(the lexicographically smallest string of concatenations of \(j\) strings chosen from \((S_1,\ldots,S_i)\)),
with transition
\(dp[i][j] = \min(dp[i-1][j], \underset{k \lt i}{\min}(dp[k][j-1] \oplus S_i))\).
The answer is \(dp[N][K]\).

The answer for the following case is bbababb, but it outputs bbababbab.

4 3
bbaba
bba
b
b

---

Correct solution

In order to remove the constraints of “arbitrary order,” we will try sorting \((S_1,\ldots,S_N)\) beforehand.
It is sufficient that, after sorting, \(S_i \oplus S_j \leq S_j \oplus S_i\) for all \(i,j(i\lt j)\).
We can prove that such a permutation always exists, and can be obtained only repeating swapping adjacent terms.

Why?

Consider a comparison of strings \(A\) and \(B\).
If we regard the strings as integers \(a\) and \(b\) written in base \(26\), we have the following transformation:

\(A \oplus B \lt B \oplus A\)
\(\Leftrightarrow a \times 26^{|B|} + b \lt b \times 26^{|A|} + a\)
\(\displaystyle \Leftrightarrow \frac{a}{26^{|A|} -1} \lt \frac{b}{26^{|B|} -1}\)

So we can see that we can sort the strings as if we sort the numbers, each of which depends only on itself.

Therefore, we sort \((S_1, \ldots,S_N)\) so that \(S_i \oplus S_{i+1} \leq S_{i+1}\oplus S_i\).

Next, we define DP by
\(dp[i][j] := \)(the lexicographically smallest string of concatenations of \(j\) strings chosen from \((S_i,\ldots,S_N)\)).
Then the following recurrence relations hold: \(dp[i][j] = \min(dp[i+1][j], S_i \oplus dp[i+1][j-1])\).

Why?

Consider \(dp[i][j]\).

• If \(S_i\) is not used, then \(dp[i][j] = dp[i+1][j]\).
• If \(S_i\) is used, then \(dp[i][j] = S_i \oplus dp[i+1][j-1]\).

The answer is \(dp[1][K]\). The complexity is \(O(NK^2 \max|S_i|)\).