Подсчет смежных перестановок, необходимых для преобразования одной перестановки в другую

Нам даны две последовательности строчных букв латинского алфавита. {{1 }} Они имеют одинаковую длину и одинаковое количество заданных типов букв (первый имеет такое же количество t, что и второй, и поэтому ). Мы обязаны найти минимальное количество перестановок ( под «перестановкой» мы подразумеваем изменение порядка двух соседних букв), необходимого для преобразования первой последовательности во вторую. Мы можем с уверенностью предположить, что каждые две последовательности МОГУТ быть преобразованы друг в друга. Мы могли бы сделать это с помощью грубой силы, но последовательности слишком длинные для этого.

Входные данные:
Длина последовательностей (минимум 2, максимум 999999) и , затем две последовательности.

Вывод:
Целое число, представляющее количество замен, необходимых для того, чтобы последовательности стали то же самое.

Пример:
{5, aaaaa, aaaaa} должен вывести {0 },
{4, abcd, acdb} должен вывести {2}.

Первое, что пришло мне в голову, - это пузырьковая сортировка. Мы можем просто отсортировать последовательность по пузырькам, подсчитывая каждый обмен. Проблема в следующем: а) это O (n ^ 2) в худшем случае б) Я не уверен, что это даст мне наименьшее число для каждого случая ... Даже оптимизированная пузырьковая сортировка, похоже, не помогает.Мы могли бы реализовать сортировку коктейлей, которая решила бы проблему с черепахами - но даст ли она мне лучшую производительность? Или, может быть, есть что-то более простое / быстрое?

Этот вопрос также можно сформулировать так: Как мы можем определить расстояние редактирования между двумя строками, когда единственная разрешенная операция - это транспонирование?