Разбор и сжатие строк

В этой теме мы разбираем строки вручную: сжимаем, вычисляем выражения, проверяем скобки и выясняем цену сборки строки. Всё решается одной схемой: проход по строке с небольшим состоянием, поэтому время O(n). Предыдущая тема: палиндромы и анаграммы.

Кодирование длин серий (RLE)

Серия — это подряд идущие одинаковые символы. RLE заменяет каждую серию на символ + число. Алгоритм: сравниваем s[i] с s[i - 1], увеличиваем счётчик, при конце серии пишем её в результат. Последняя серия записывается после цикла. Время O(n), память O(n). Выигрыш на длинных сериях ("a" * 100 → a100), проигрыш на одиночных символах (abc → a1b1c1, вдвое длиннее).

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

import re

def rle_decode(t):
    return "".join(ch * int(n) for ch, n in re.findall(r"(\D)(\d+)", t))