*Bounty: 50*

*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.