Сожми строку RLE-кодированием

RLE (run-length encoding) — задача на скрининге уровня middle: проверяют, аккуратно ли ты держишь состояние в цикле и не забываешь ли про краевые случаи. Алгоритм наивно простой, но именно на краях люди и спотыкаются — последняя серия символов теряется чаще всего.

Задача

RLE-кодирование сжимает подряд идущие одинаковые символы в пару «сколько раз + сам символ». Например, WWWWWWWWW превращается в 9W.

Напиши функцию rle_encode(s), которая кодирует строку. Проверь на:

• 'WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW' → '9W3B24W1B14W'
• 'ABCABCABCDDDFFFFFF' → '1A1B1C1A1B1C1A1B1C3D6F'

Решение

def rle_encode(s):
    if not s:
        return ""
    count = 1
    result = ""
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            count += 1
        else:
            result += str(count) + s[i]
            count = 1
    result += str(count) + s[-1]
    return result


cases = [
    "WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW",
    "ABCABCABCDDDFFFFFF",
    "AAAA",
    "",
]
for s in cases:
    print(f"{s!r} -> {rle_encode(s)!r}")

Разбор

Идея — идти по строке и копить счётчик, пока текущий символ совпадает со следующим. Как только сосед отличается — серия закончилась: дописываем в результат «счётчик + символ» и сбрасываем счётчик в единицу.

Ключевой приём — сравнивать не «текущий с предыдущим», а s[i] c s[i + 1]. Поэтому цикл идёт до len(s) - 1: у последнего символа нет соседа справа, обращение к s[i + 1] вышло бы за границу. Это и есть первая ловушка.

Вторая, самая частая, — потерянная последняя серия. Внутри цикла мы дописываем серию только в момент смены символа. Но у последней серии смены не происходит — строка просто кончается. Поэтому после цикла обязательна строка result += str(count) + s[-1], которая закрывает хвост. Убери её — и '9W3B24W1B14W' превратится в '9W3B24W1B', потеряв финальные 14W. На собеседовании прогон именно последней серии в голове — то, что отличает аккуратное решение от «вроде работает».

Третья ловушка — пустая строка. Без охраны if not s строка s[-1] в конце упадёт с IndexError, ведь брать последний символ не из чего. Одна проверка в начале закрывает этот случай — возвращаем пустую строку. Собеседующий любит спросить «а что на пустом входе?», и готовый ответ тут ценится.

По формату вывода: владелец ноутбука кодирует как «число, потом буква» (9W), поэтому 'ABC...' даёт '1A1B1C...' — одиночные символы тоже получают счётчик 1. Это делает кодирование однозначно обратимым, хотя для строк без повторов RLE, наоборот, раздувает длину — что тоже стоит проговорить: сжатие выгодно только на данных с длинными сериями.

Сложность — O(n): один проход по строке. Родственная задача на посимвольный разбор — проверка анаграмм, где вместо серий считают общий состав букв.

Ожидаемый результат

'WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW' -> '9W3B24W1B14W'
'ABCABCABCDDDFFFFFF' -> '1A1B1C1A1B1C1A1B1C3D6F'
'AAAA' -> '4A'
'' -> ''