I'm currently thinking about the following problem.
Input: a set $W$ of strings over an alphabet $\Sigma$.
Goal: permute the characters in each string so that the trie that will contain the rearranged strings has as few edges as possible.
(by "permuting" and "rearranging", I mean that any permutation of the characters is valid).
Given strings $S=$"ABRACADABRA" and $T=$"BARRACUDA", storing them without rearrangement would require a trie of size 20, since they share no common prefix; however, if we are allowed to rearrange them, we can obtain the following optimal solution of size 12:
0-A-B-R-A-C-A-D-R-A-B-A (S') \ U (T')
(where 0 denotes the root, and $S'$ (resp. $T'$) is the rearranged $S$ (resp. $T$)).
Has this problem been studied before, and can you give me references? What is its complexity (for $|W|\geq 3$; the problem is easy otherwise)?