#StackBounty: #algorithms #strings #string-metrics #edit-distance Edit distance of list with unique elements

Bounty: 50

Levenshtein-Distance edit distance between lists
is a well studied problem.
But I can’t find much on possible improvements if
it is known that no element does occurs more than once in each list.

Let’s also assume that the elements are comparable/sortable
(but the lists to compare are not sorted to begin with).

In particular I am interested
if the uniqueness of elements makes it possible to improve upon
Ukkonen’s algorithm for edit distance
which has time complexity $O(min(m,n)s)$ and
space complexity $O(min(s,m,n)s)$,
where $s$ is the minimum cost of the editing steps.

More formally,

how efficiently can we compute the edit distance between two given strings
$s,t in Sigma^*$
with the promise that they don’t have any repeated letters?

$Sigma$ is a very large alphabet.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.