Сжатие повторяющихся символов в строке

46. Сжатие повторяющихся символов в строке

Условие задачи:
Написать функцию curtail_str(letters: str) -> str, которая сжимает строку по сериям подряд идущих одинаковых символов.

Правила:

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

Примеры:

"" -> ""
"ABC" -> "ABC"
"AAA" -> "A3"
"AAABBXYZDDDDA" -> "A3B2XYZD4A"
"ABCABCABCCCCC" -> "ABCABCABC5"

Код задачи:

def curtail_str(letters: str) -> str:
    ...


assert curtail_str("") == ""
assert curtail_str("ABC") == "ABC"
assert curtail_str("AAA") == "A3"
assert curtail_str("AAABBXYZDDDDA") == "A3B2XYZD4A"
assert curtail_str("ABCABCABCCCCC") == "ABCABCABC5"

print("done")

Дополнительно:

Почему в result выбран тип данных str?
Оцени свой алгоритм с точки зрения On

Спойлеры к решению

Подсказки

Нужно идти по строке слева направо.
Нужно хранить текущий символ и количество его подряд идущих повторений.
Если следующий символ такой же — увеличиваем счётчик.
Если следующий символ другой — записываем предыдущую группу в результат.
Если символ встретился один раз, записываем только символ.
Если символ повторился несколько раз, записываем символ и количество.
Для результата лучше использовать список, а в конце собрать строку через "".join(...).

Решение

def curtail_str(letters: str) -> str:
    if not letters:
        return ""

    result = []

    current_char = letters[0]
    count = 1

    for char in letters[1:]:
        if char == current_char:
            count += 1
        else:
            if count == 1:
                result.append(current_char)
            else:
                result.append(f"{current_char}{count}")

            current_char = char
            count = 1

    if count == 1:
        result.append(current_char)
    else:
        result.append(f"{current_char}{count}")

    return "".join(result)

Проверка:

assert curtail_str("") == ""
assert curtail_str("ABC") == "ABC"
assert curtail_str("AAA") == "A3"
assert curtail_str("AAABBXYZDDDDA") == "A3B2XYZD4A"
assert curtail_str("ABCABCABCCCCC") == "ABCABCABC5"

print("done")

Результат:

done

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

"AAABBXYZDDDDA"

Строка разбивается на подряд идущие группы:

AAA -> A3
BB  -> B2
X   -> X
Y   -> Y
Z   -> Z
DDDD -> D4
A   -> A

Итог:

A3B2XYZD4A

Почему result лучше делать списком, а не строкой:

result = []

Функция должна вернуть строку, но собирать результат через список эффективнее. Если делать так:

result += piece

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

Поэтому лучше добавлять части в список:

result.append(piece)

а в конце один раз собрать строку:

return "".join(result)

Оценка сложности:

Время: O(n)
Память: O(n)

n — длина входной строки. Алгоритм проходит по строке один раз, поэтому время работы линейное. Дополнительная память нужна для списка частей результата.