I'm looking for the most efficient way of solving an Levenshtein edit distance problem.

We are given as input:

  1. A set of strings S of size n <= 8, with average length m <= 50
  2. A target string t of length l <= 50

Our task is to 'align' t with S i.e:

Find the subset s* of S, where concat(s*) has the minimum Levenshtein edit distance (among all the subsets) with t

Some thoughts:

  1. For 2 strings of length l1 and l2, we could use the standard dynamic programming algorithm which has O(l1*l2) time complexity
  2. Brute forcing this would require us to compute editDistance(t, concat(s')) for each subset s'. This would be approximately O(l.m.n!)
  3. This could be optimized a bit by memoizing the results i.e if we are computing editDistance(t, S[1, 2, 3, 4]) we could re-use the computation from S[1, 2, 3])
  4. The other option I could think of is to construct a Trie or DAWG (Directed Acyclic Word Graph)

But, I'm not an expert on this, so I might be missing a better solution. How would we do this efficiently?

Thanks in advance!

  • $\begingroup$ It is a good question. Could you please give reference to where you find this problem? $\endgroup$ Commented Aug 3, 2023 at 21:57
  • $\begingroup$ What are the constraints on the running time of the algorithm? $\endgroup$ Commented Aug 4, 2023 at 10:25
  • 1
    $\begingroup$ Concatenation is not defined for a set. Do you mean "among all permutations" or is S a sequence ? $\endgroup$
    – user16034
    Commented Sep 3, 2023 at 18:26
  • 1
    $\begingroup$ If the strings in s, and t have roughly the same length, most minimal matchings should be with a single string, because m deletions (to reach the same length) compete with m substitutions. $\endgroup$
    – user16034
    Commented Sep 3, 2023 at 18:32

1 Answer 1


Try all possible permutation and combination of the set $S$. There are exactly $\sum_{r = 1} ^{8} \mathsf{8Pr}$ such possibilities for $n = 8$. This sums to exactly 109600.

For each subset $s^*$ of $S$, find the edit distance to target string $t$ using the standard DP algorithm. This will take time $l_S \times l$ where $l_S$ is the total length of all the strings in $S$ and $l$ is the length of string $t$. Since $l_S$ could be $400$ and $l$ could be $50$, the total running time is ~ $ 2 \times 10^9$.

You can further optimize the algorithm. In the standard DP algorithm, the algorithm stores the minimum edit distance of all the pairs of suffixes of two given strings $a$ and $b$. In the current problem, the string $t$ is fixed; however $concat(s^*)$ varies depending on subset $s^*$. However, note that some suffixes of $concat(s^*)$ overlaps for different $s^*$. You can show that there at most $S_l \cdot (nC0 + nC1 + nC2 + \dotsc + nCn)$ possible different suffixes of the concatenated string $concat(s^*)$ over all possible subsets $s^{*}$ for $n = 8$. This sums to at most $S_l \cdot 2^{8} \leq 102400$. Thus, the algorithm only needs to find edit distance of $102400 \times 50$ possible pairs of suffixes. Thus, the algorithm can be implemented in ~ $5 \times 10^{6}$ computation steps, which is doable in $1$ sec on regular personal computers.

  • $\begingroup$ By augmenting the standard DP with an extra "column" of edges for each $s_i$ that deletes that entire string for zero cost, it's possible to consider only concatenations of permutations that use all 8 strings in $S$. This drops the number of possibilities from 109600 to $8! = 40320$. $\endgroup$ Commented May 2 at 0:16

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.