1. Идея

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

Например:

• a остается a
• aaaaaaab превращается в ab
• aabcccdaa превращается в abcda

Самая простая идея: пройти по строке слева направо и добавлять очередной символ в ответ только тогда, когда он отличается от предыдущего.

2. Наблюдения

1. Если символ s[i] совпадает с s[i - 1], то он находится в той же группе повторов, что и предыдущий, значит добавлять его не нужно.

2. Если символ s[i] не равен s[i - 1], значит началась новая группа одинаковых символов, и этот символ нужно добавить в ответ.

3. Первый символ строки всегда должен попасть в ответ, потому что он открывает первую группу.

4. По условию строка непустая, поэтому можно сразу взять s[0] как первый символ ответа.

3. Алгоритм

1. Считать строку s.
2. Создать строку ответа, в которую сначала записать s[0].
3. Для всех позиций от 1 до len(s) - 1:
   • если s[i] != s[i - 1], добавить s[i] в ответ.
4. Вывести ответ.

4. Почему это работает

Рассмотрим любую группу подряд идущих одинаковых символов.

Например, в строке aaabbccccd есть группы:

• aaa
• bb
• cccc
• d

Алгоритм работает так:

• первый символ каждой группы добавляется в ответ;
• все остальные символы этой же группы равны предыдущему, поэтому пропускаются.

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

Других символов алгоритм не удаляет: если символ отличается от предыдущего, он начинает новую группу и обязательно добавляется.

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

5. Сложность

Пусть длина строки равна n.

• Время: O(n), потому что строка просматривается один раз.
• Память: O(n) на хранение ответа.

6. Код на C++17

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;

    string ans;
    ans += s[0];

    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i] != s[i - 1]) {
            ans += s[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

s = input()

ans = [s[0]]
for i in range(1, len(s)):
    if s[i] != s[i - 1]:
        ans.append(s[i])

print("".join(ans))