требуется минимум свопов, чтобы убедиться, что в соседнем месте нет двух кошек или собак

Question

нам дан массив и элементы массива представляют кошек и собак. Мы должны переставить элементы, меняя местами так, чтобы в соседнем месте не было двух кошек или собак.

Примечание. Мы можем поменять элемент массива на любой элемент.

Eg: given input: [d,c,d,c,c]
exp o/p: 2
Explanation : 
step 1: swap index-0 and index-1 =>[c,d,d,c,c]
step 2: swap index2 and index-3  =>[c,d,c,d,c]

input: [c,d,d,c,c,c]
exp o/p : not possible

Answer 1

1. Проверьте, является ли какой-либо из них n == m + 1 или n == m истинно.
2. Если это не так, это невозможно, и return.
3. Еслиn == m + 1 мы знаем, что для всех четных индексов должен быть n, а для всех нечетных - m.
4. РЕДАКТИРОВАТЬ: Если n == m начальное значение имеет значение!Если количество перестановок является наиболее важной частью алгоритма, выполните шаг 5 для обоих возможных вариантов и сравните длину результирующих подмассивов. [1] Спасибо @Ishpreet за указание на это!
5. Выполните итерацию по массиву, проверьте, есть ли n или m.Если значение неверно для соответствующего индекса (например, в индексе 0 вместо n есть m, обратите внимание, что индекс либо в массиве для неправильно размещенных n's, либо m's.
6. После этого поменяйте местами записанные значения индекса в массиве на основе двух вложенных массивов.

[C, C, C, C, D, D, D, D]

Неверно C = [1, 3]

Неверно D = [4, 6]

Своп (1,4) и (3,6)

Результат: [C, D, C, D, C, D, C, D]

[1] Сложность алгоритма неиз-за этого.