Минимальное количество свопов для преобразования строки в другую строку

Проблема:

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

min_swaps('kamal', 'amalk') -> 3
#       1         2        3
# kamal -> lamak -> aamlk -> amalk

Примечание. На SO есть много таких вопросов, но ни один из них не применяется к произвольным свопам.

Начальный подход:

let s1 = 'kamal'
let s2 = 'amalk'

Предположим, что s1 является "правильным" упорядочением, то есть его элементы отображают последовательность из 0 -> N-1 в порядке возрастания.

0 1 2 3 4
k a m a l

Теперь создайте массив P, который является отображением из букв в s2 в правильный индекс в s1:

1 2 3 4 0
a m a l k 

P = [1,2,3,4,0]

Теперь мы можем подсчитать количество инверсий массива в P с помощью модифицированной слияния, которая даст нам количество элементов, которые не соответствуют порядку.

Модифицированный mergesort:

int main(int argc, char ** argv) {
   int array[] = { 1,2,3,4,0 };

   int array_size = sizeof(array)/sizeof(array[0]);
   int inversions = merge_sort(array, 0, array_size - 1);

   printf("Found %d inversions\n", inversions);
   return 0;
}

int merge_sort(int a[], int start, int end) {
   if ( end > start ) {
      int mid = start + (end - start) / 2;
      int x = merge_sort(a, start, mid);
      int y = merge_sort(a, mid + 1, end);
      int z = merge(a, start, mid, end);

      return x + y + z;
   }

   return 0;
}

int merge(int a[], int start, int mid, int end) {
   int l = start, r = mid + 1;
   int i = 0;
   int temp[end - start + 1];
   int splitInversionCount = 0;

   while ( l <= mid && r <= end ) {
       if ( a[l] < a[r] ) {
          temp[i++] = a[l++];
       }
       else {
         splitInversionCount += mid - l + 1;
         temp[i++] = a[r++];
       }
   }

   // copy whichever half of the array remains
   while ( l <= mid ) {
      temp[i++] = a[l++];
   }

   while ( r <= end ) {
      temp[i++] = a[r++];
   }

   // copy temp back into a
   int k;
   for(k = 0; k < i; k++) {
      a[k + start] = temp[k];
   }

   return splitInversionCount;
}

---

Проблема заключается в том, что он дает минимальное количество свопов только с соседними элементами, это возвращает 4 вместо 3.

Вопрос:

Есть ли способ расширить этот алгоритм для захвата произвольных свопов? Или мне нужен совершенно другой подход?