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