Hints: Compress Strings

First, let’s assume that the input does not contain a string that occurs as a substring in the input. Without worrying about the minimum length, can you generate one string that is guaranteed to have all the strings as substrings?

Simply concatenating all the strings is one valid choice. In fact, all the n! permutations are valid choices. Now, for a given permutation, how do we reduce its length to as small as possible?

If in the permutation, string i is to the left of string j, then we can remove some prefix of string j. What is that prefix?

The longest prefix of string j that appears as a suffix of string i can safely be removed. Let’s count the remaining suffix of str[j] and call it merge_cost. Let’s build a complete graph where the edge weight between nodes i to j is equal to the merge cost if we append string j to the right of string i. What do you need to find out in this graph?

In this graph, you are interested in a path that visits each vertex exactly once and has the minimum weight. This is nothing but the Travelling Salesman Problem, which can be done via Bitmask DP.

The only thing remaining is how to efficiently compute the merge cost when str[j] is appended after str[i]. For this, you can try CF1200E : Compress Words

Compute the prefix function of str[j] + $ + str[i]. The last element of the prefix function is the length of the longest prefix of str[j] which is also a suffix of str[i]. You can use Prefix function from Atcoder Library.

Our algorithm works, but only when the input doesn’t contain a string that is already present as a substring of other strings. How do we reduce the input to this version?

It’s simple. Checking if a string is part of another string can be done in O(TEXT + PATTERN) via the Prefix function. So, just iterate over all pairs, and if s[i] is a substring of s[j], simply remove s[i].