1. Идея

Нужно реализовать сжатие строки по правилам RLE.

Мы идём по строке слева направо и разбиваем её на максимальные подряд идущие группы одинаковых символов. Для каждой такой группы:

• если длина группы равна 1 и символ не является цифрой, то в ответ добавляем только этот символ;
• иначе добавляем сначала длину группы в десятичной записи, потом сам символ.

Особый случай с цифрами очень важен: даже одиночная цифра '7' должна кодироваться как 17, а не как просто 7.

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

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

1. Каждая позиция строки принадлежит ровно одной группе одинаковых символов.

2. Если начать в позиции i, то можно двигать указатель j вправо, пока s[j] == s[i]. Тогда отрезок от i до j - 1 и будет одной максимальной группой.

3. После обработки группы можно сразу перейти к следующей, то есть присвоить i = j.

4. Для одиночной группы:

   • символ 'a' кодируется как a;
   • символ '7' кодируется как 17.

5. Ограничение до 10^5 символов требует линейного решения. Полный перебор или какие-то сложные структуры здесь не нужны.

3. Алгоритм

Пусть дана строка s.

1. Создаём пустой список частей ответа.
2. Заводим индекс i = 0.
3. Пока i < n:
   • ставим j = i;
   • пока j < n и s[j] == s[i], увеличиваем j;
   • теперь длина текущей группы равна j - i, а её символ — s[i].
4. Кодируем группу:
   • если длина равна 1 и символ не цифра, добавляем только этот символ;
   • иначе добавляем строку из длины группы и символа.
5. Переходим к следующей группе: i = j.
6. В конце склеиваем все части и выводим результат.

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

Докажем, что алгоритм строит именно ту строку, которую должен выдать архиватор.

Рассмотрим любой шаг алгоритма, когда указатель стоит в позиции i.

• Внутренний цикл находит наибольший индекс j, такой что все символы от i до j - 1 равны s[i].
• Значит, подстрока s[i..j-1] — это максимальная подряд идущая группа одинаковых символов.
• Именно на такие группы по условию и должна разбиваться строка.

Дальше алгоритм кодирует эту группу строго по правилам задачи:

• если длина группы 1 и символ не цифра, записывается только символ;
• во всех остальных случаях записывается длина группы и затем символ.

Это полностью совпадает с описанием архиватора.

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

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

5. Сложность

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

• Каждый символ посещается указателем j не более одного раза.
• Указатель i тоже проходит строку слева направо.

Поэтому общая временная сложность равна O(n).

Дополнительная память:

• O(n) на хранение частей ответа и итоговой строки.

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

    vector<string> parts;
    int n = (int)s.size();
    int i = 0;

    while (i < n) {
        int j = i;
        while (j < n && s[j] == s[i]) {
            j++;
        }

        int len = j - i;
        char c = s[i];

        if (len == 1 && !(c >= '0' && c <= '9')) {
            parts.push_back(string(1, c));
        } else {
            parts.push_back(to_string(len) + string(1, c));
        }

        i = j;
    }

    string ans;
    for (const string& part : parts) {
        ans += part;
    }

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

7. Код на Python 3

s = input().strip()

parts = []
n = len(s)
i = 0

while i < n:
    j = i
    while j < n and s[j] == s[i]:
        j += 1

    length = j - i
    c = s[i]

    if length == 1 and not ('0' <= c <= '9'):
        parts.append(c)
    else:
        parts.append(str(length))
        parts.append(c)

    i = j

print(''.join(parts))