Сжатие строки (Run-Length Encoding)

Сжатие строки (Run-Length Encoding)

Это задача на обработку строк с группировкой последовательных символов. Нужно заменить последовательности одинаковых символов на символ+счётчик.

Решение 1: Простой проход (рекомендуется)

Идём по строке, считаем последовательные одинаковые символы.

def compress(s: str) -> str:
    # Обработка пустой строки
    if not s:
        return s
    
    compressed = []
    count = 1
    
    for i in range(1, len(s)):
        # Если следующий символ отличается
        if s[i] != s[i - 1]:
            # Добавляем предыдущий символ и его счётчик
            compressed.append(s[i - 1])
            compressed.append(str(count))
            count = 1
        else:
            # Увеличиваем счётчик
            count += 1
    
    # Добавляем последний символ
    compressed.append(s[-1])
    compressed.append(str(count))
    
    return ''.join(compressed)

# Примеры
print(compress("aabcccccaaa"))  # a2b1c5a3
print(compress("abc"))          # abc
print(compress("aaaa"))         # a4
print(compress(""))             # 

Как работает на "aabcccccaaa":

i=1: s[1]='a' == s[0]='a' → count=2
i=2: s[2]='b' != s[1]='a' → добавляем 'a','2' → count=1
i=3: s[3]='c' != s[2]='b' → добавляем 'b','1' → count=1
i=4: s[4]='c' == s[3]='c' → count=2
i=5: s[5]='c' == s[4]='c' → count=3
i=6: s[6]='c' == s[5]='c' → count=4
i=7: s[7]='c' == s[6]='c' → count=5
i=8: s[8]='a' != s[7]='c' → добавляем 'c','5' → count=1
i=9: s[9]='a' == s[8]='a' → count=2
i=10: s[10]='a' == s[9]='a' → count=3
Конец: добавляем 'a','3'

Результат: a2b1c5a3

Сложность:

• Время: O(n) — один проход
• Память: O(n) в худшем случае (если нет повторений)

Решение 2: Проверка размера перед сжатием

Частый требование — не возвращать сжатую строку, если она не короче.

def compress_with_check(s: str) -> str:
    # Сначала проверяем, будет ли сжатая строка короче
    compressed_size = 0
    count = 1
    
    for i in range(1, len(s)):
        if s[i] != s[i - 1]:
            # Символ + его длина
            compressed_size += 1 + len(str(count))
            count = 1
        else:
            count += 1
    
    # Учитываем последний символ
    compressed_size += 1 + len(str(count))
    
    # Если не короче, возвращаем исходную
    if compressed_size >= len(s):
        return s
    
    # Иначе сжимаем
    return compress(s)

print(compress_with_check("abc"))          # abc (не сжимаем)
print(compress_with_check("aabcccccaaa"))  # a2b1c5a3 (сжимаем)

Решение 3: С использованием itertools.groupby (pythonic)

idea: использовать встроенный инструмент для группировки.

from itertools import groupby

def compress_groupby(s: str) -> str:
    result = []
    for char, group in groupby(s):
        count = len(list(group))
        result.append(char + str(count))
    
    return ''.join(result)

print(compress_groupby("aabcccccaaa"))  # a2b1c5a3
print(compress_groupby("abc"))          # a1b1c1

Минусы: всегда добавляет счётчик, даже если он "1".

Улучшенная версия:

from itertools import groupby

def compress_groupby_v2(s: str) -> str:
    result = []
    for char, group in groupby(s):
        count = len(list(group))
        result.append(char)
        if count > 1:
            result.append(str(count))
    
    return ''.join(result)

print(compress_groupby_v2("aabcccccaaa"))  # a2b1c5a3 (ждите, тут b1 всё ещё)
print(compress_groupby_v2("abc"))          # abc (правильно!)

Этот вариант нужно уточнить в требованиях.

Решение 4: Однопроходная версия с оптимизацией памяти

Вместо списка используем string concatenation (медленнее для больших строк).

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

Минусы: медленнее (string concatenation создаёт новые объекты в Python).

Решение 5: Декомпрессия (обратная операция)

Также полезно знать, как распаковать сжатую строку:

def decompress(s: str) -> str:
    result = []
    i = 0
    
    while i < len(s):
        char = s[i]
        i += 1
        
        # Читаем число
        count_str = ""
        while i < len(s) and s[i].isdigit():
            count_str += s[i]
            i += 1
        
        count = int(count_str) if count_str else 1
        result.append(char * count)
    
    return ''.join(result)

print(decompress("a2b1c5a3"))   # aabcccccaaa
print(decompress("abc"))        # abc
print(decompress("a3b2c1"))     # aaabbc

Решение 6: С обработкой многозначных чисел

Что если символ повторяется 12 раз? (a12)

def compress_multi_digit(s: str) -> str:
    if not s:
        return s
    
    compressed = []
    count = 1
    
    for i in range(1, len(s)):
        if s[i] != s[i - 1]:
            compressed.append(s[i - 1])
            compressed.append(str(count))
            count = 1
        else:
            count += 1
    
    # Последний символ
    compressed.append(s[-1])
    compressed.append(str(count))
    
    return ''.join(compressed)

print(compress_multi_digit("aaaaaaaaaaaa"))  # a12 (12 a-шек)
print(compress_multi_digit("aabcccccaaa"))   # a2b1c5a3

Это работает автоматически благодаря str(count).

Тестовые случаи

def test_compress():
    assert compress("aabcccccaaa") == "a2b1c5a3"
    assert compress("abc") == "abc"
    assert compress("") == ""
    assert compress("a") == "a1"
    assert compress("aa") == "a2"
    assert compress("aaaa") == "a4"
    assert compress("abcdef") == "a1b1c1d1e1f1"
    assert compress("aaaaabbbcccd") == "a5b3c3d1"
    print("Все тесты пройдены!")

test_compress()

Сравнение решений

На собеседовании

Используй первое решение — оно:

• Понятное и читаемое
• O(n) по времени
• Не требует дополнительных импортов
• Легко объяснить шаг за шагом

Если спросят про оптимизацию:

• Можно проверить размер до сжатия (решение 2)
• Можно использовать groupby для компактности
• Можно обсудить dekompression (решение 5)

Это хороший вопрос, показывающий базовые навыки работы со строками и циклами.