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.
Edit distance of list with unique elements
algorithms;strings;string metrics;edit distance