计算将一个排列转换为另一个排列所需的相邻交换

Question

我们给了两个小写拉丁字母序列。它们的长度相同，给定类型的字母数量相同（第一个字母与第二个字母具有相同数量的t，依此类推）。我们需要找到将第一个序列转换为第二个序列所需的最少交换次数（“交换”是指更改两个相邻字母的顺序）。我们可以安全地假设每两个序列可以相互转换。我们可以用蛮力来做到这一点，但是序列太长了。

输入：

序列的长度（至少2个，最大999999），然后是两个序列。

输出：

一个整数，表示序列变得相同所需的交换次数。

示例：

{5，aaaaa，aaaaa}应该输出{0}，

{4，abcd，acdb}应该输出{2}。

我想到的第一件事是冒泡。我们可以简单地对排序每个交换的序列进行冒泡排序。问题是：a）是O（n ^ 2）最坏的情况b）我不相信在每种情况下它都会给我最小的数字...即使是优化的冒泡现象也似乎并不能解决问题。我们可以实施鸡尾酒解决方案来解决乌龟的问题-但这会给我带来最佳表现吗？也许有更简单/更快的东西？

这个问题也可以表述为：当唯一允许的操作是移调时，如何确定两个字符串之间的编辑距离？