Знающие людиии помогите! )

Question

У Робота есть строка, состоящая из латинских строчных букв a, b, c. Он сокращает эту строку по следующему правилу: просматривает е слева направо, если встречает четыре подряд идущие символа типа XOXO (вместо X стоит один и тот же символ, вместо O стоит один и тот же символ, отличный от X, например, abab или caca) , он их удаляет, “склеивая” оставшуюся строку в месте разрыва. После удаления символов Робот возвращается к началу строки и опять просматривает е слева направо и т. д, пока пройдя по строке он не сможет найти подстроки, которую можно удалить.
Например, из строки ababcbcbb после первого просмотра робота получится строка cbcbb, а после второго строка b.
У Робота была строка, которую такими действиями можно полностью удалить. Однако из не случайно стерли одну букву. Вот, что осталось:

abababbccbcbababcaabcbcbabc

Помогите Роботу восстановить строку. В качестве ответа нужно вывести пару буква и число, разделенные пробелом, где буква – это потерянная буква (латинская строчная a, b или c) , а число – номер этой буквы в строке. Если вариантов несколько, выведите тот, где номер буквы наименьший.

Пример. Если бы вам была дана строка abb, то ответ был бы таким: a 3.

Answer 1

Букву можно определить просто посчитав количество повторений каждой буквы в строке. Одна из букв повторится нечётное количество раз, вот её и удалили. А позицию, из которой эту букву удалили, посчитать уже сложне.

Если изначально можно было удалить всю строку, значит расстояние между любыми двумя одинаковыми буквами было кратно двум. Так местонахождение недостающей буквы можно локализовать подсчитывая расстояния между одинаковыми буквами. Как только мы найдём 2 одинаковые буквы, на расстоянии не кратном двум, значит между ними и была удалённая. И если я не ошибаюсь, то проверив так абсолютно все буквы, мы сможем однозначно определить позицию удалённой (но тут не уверен, возможно и не сможем, и придётся выполнять ещё какие-то проверки. так глубоко в эту задачу лень вникать) .

Если же расстояния между всеми ближайшими парами букв верны, значит удалённая буква была или первой или последней. Но это не имет значения, ведь если у нас получилось в остатке aba, то устроит нас и baba и abab . ) Значит мы считаем что буква удалена из первой позиции .