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