あまり考察をせずに解く方法です。 計算量も公式解説のものと比べたら悪いです。

まず、同じ長さの文字列は最も辞書順が小さいものだけを採用すればいいので、考えるべき文字列は \(10\) 種類以下になるので、\(N \leq 10\) としても良いです。

\(dp[n][i][j]\) を以下のように定義します。

• 答えの \(n\) 文字目が \(S_{i}\) の \(j\) 文字目に対応するような文字列の繋げ方が存在するか、存在するなら、今まで使った文字列の数の最大値。存在しないなら \(-1\)

\(dp[n]\) がわかっているとき、\(dp[n + 1][i][j]\) は以下のルールで更新します。

• \(j \neq |S_{i}|\) ならば、\(dp[n + 1][i][j + 1] = dp[n][i][j]\)
• \(j = |S_{i}|\) かつ \(dp[n][i][j] \neq -1\) であるような \(i\) が存在するなら、そのような \(i\) のうち \(dp[n][i][j]\) が最大のものを選び、任意の \(k\) に対して \(dp[n + 1][k][1] = dp[n][i][j] + 1\)

その後、\(dp[n + 1][i][j]\neq -1\) を満たす \((i, j)\) のうち、\(S_{i, j}\) の最小値 \(m\) を取り、それを答えの文字列の末尾に加えた後、\(S_{i, j}\neq m\) を満たす \((i, j)\) に対して、\(dp[n + 1][i][j] = -1\) とします。

この \(dp\) の更新を繰り返し、\(dp[n][i][|S_{i}|] = K\) となるような \((n, i)\) が見つかれば探索を打ち切れば良いです。

計算量は文字列の長さの上限を \(L\) として、\(O(L^{3}K)\) です。

実装例 C++