Дана цепочка красных и синих шаров, найдите минимальное количество перестановок, чтобы соединить цвета вместе.

Нам дана строка вида: RBBR, где R - красный, а B - синий.

Нам нужно найти минимальное количество замен, необходимых для объединения цветов вместе. В приведенном выше случае ответом будет 1 , чтобы получить RRBB или BBRR.

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

Есть идеи?

Согласно this , это предположительно вопрос из интервью Microsoft.