Resolví este problema usando hashing. El hashing puede fallar en algunos casos y existen algunos trucos para disminuir la probabilidad de que esto pase. De todas formas, mi solución pasó los ~Casos de Prueba~ =P.

Siendo las cadenas de la entrada ~s_1, s_2, s_3~. Podemos construir la solución más pequeña permutando las cadenas y luego tratando de 'unirlas' una a la otra. Para dos cadenas ~a~ y ~b~, necesitamos encontrar el segmento más largo que se solapa entre el final de la cadena ~a~ y el inicio de la cadena ~b~. La fuerza bruta obvia no dará en tiempo. Sin embargo, podemos usar hashing para calcular el resultado en ~O(n)~, donde ~n~ es ~min(len(a), len(b))~. La función de hashing que usé es la polinomial ~hash(x_0, x_1, ..., x_n) = x_0 + ax_1 + a^2x_2 + ... + a^nx_n~. Esto nos ofrece la oportunidad de calcular el valor de hash de cualquier subsequiencia de la cadena en tiempo ~O(1)~.

Entonces, podemos intentar todas las permutaciones de ~s_1, s_2, s_3~ e intentar 'unir' las cadenas adyacentes eliminando los segmentos que se solapan entre estas utilizando la idea anterior explicada.

Existe un último caso: si ~s_i~ es una substring de ~s_j~ para cualquier ~i \neq j~, entonces simplemente podemos ignorar ~s_i~. Podemos usar hashing para revisar si una cadena está contenida dentro de otra.

Link del problema en Codeforces