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)?

  • 1
    $\begingroup$ What kinds of rearrangements do you permit? Arbitrary permutations? $\endgroup$ Oct 5, 2011 at 14:12
  • 1
    $\begingroup$ I had the same question as Dave. Can you edit the question so that people do not have to read the comments to understand what you are asking? $\endgroup$ Oct 5, 2011 at 15:31
  • 3
    $\begingroup$ Do you have an application in mind? $\endgroup$
    – Raphael
    Oct 5, 2011 at 17:45
  • 1
    $\begingroup$ In the graph example, you are storing sets of edges, while your question seems to suggest that you are storing multisets (i.e., your strings may contain the same character more than once). The case of sets sounds easier to me... $\endgroup$ Oct 5, 2011 at 21:56
  • 1
    $\begingroup$ Is alphabet Σ fixed or specified as part of the input? (Your comment suggests that it is part of the input.) $\endgroup$ Oct 6, 2011 at 23:39

2 Answers 2


The problem I'm wondering about was tackled long ago (1977) by Douglas Comer and Ravi Sethi, in a paper entitled "The Complexity of Trie Index Construction". They show that the decision version of the above problem, as well as three other variants, are NP-complete.


Hmm, minimizing the size of the trie seems hard. However, when you change your objective function to maximizing the saved space you can easily get a 2-approximation.

For every pair of strings, count the number of characters they have in common. Then do a max cost matching weighted by the values computed before, and for each matched pair permute their characters so that their common prefix is as long as possible. The analysis is simple, right?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.