Минимизируйте перестановку пар символов, чтобы в строке не было двух одинаковых символов.

Для заданной строки S , состоящей из N символов, задача состоит в том, чтобы найти минимальное количество пар символов, которые необходимо поменять местами, чтобы никакие два соседних символа не были одинаковыми. Если это невозможно сделать, то выведите «-1» .

Примеры:

Input: S = “ABAACD”
Output: 1
Explanation: Swapping S[3] and S[4] modifies the given string S to “ABACAD”. Since no two adjacent characters are the same, the minimum number of operations required is 1.

Input: S = “AABA”
Output: -1

Подход: Данная проблема может быть решена с помощью Backtracking. Идея состоит в том, чтобы сгенерировать все возможные комбинации перестановки пары индексов, а затем, если сгенерированная строка не содержит соседних символов, одинаковых с минимальной перестановкой, то вывести это минимальное количество выполненных операций перестановки. Выполните следующие шаги, чтобы решить проблему:

• Определите функцию minimumSwaps(string &str, int &minimumSwaps, int swaps=0, int idx) и выполните следующие операции:
  • Если соседние символы строки str различны, то обновите значение MinimumSwaps до минимума из MinimumSwaps и swaps .
  • Перебрать диапазон [idx, N], используя переменную i и выполнив следующие операции:
    • Перебрать диапазон [i + 1, N], используя переменную j и выполняя следующие операции:
      • Поменяйте местами символы в позициях i и j в строке S.
      • Вызовите функцию minimumSwaps(str, MinimumSwaps, swaps+1, i + 1) , чтобы найти другие возможные пары обменов для создания результирующей строки.
      • Поменяйте местами символы в позициях i и j в строке S.
• Инициализируйте переменную, скажем, ansSwaps как INT_MAX, чтобы сохранить количество требуемых минимальных свопов.
• Вызовите функцию minimumSwaps(str, ansSwaps), чтобы найти минимальное количество свопов, необходимых для того, чтобы все соседние символы стали разными.
• После выполнения вышеуказанных шагов, если значение ansSwaps равно INT_MAX, выведите -1 . В противном случае выведите значение ansSwaps в качестве результирующего минимального свопа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ³ *2 ^N )
Вспомогательное пространство: O(1)