String Compression

Q: Какова временная сложность сжатия строки?

Обход двумя указателями занимает O(n) времени, потому что индекс сканирования движется только вперёд. Помимо результата, он хранит два индекса, поэтому дополнительная память составляет O(1) .

ЛегкоДва указателя Массивы и строки

+10

Дана строка s, состоящая из английских букв. Сожми её: каждую последовательность из двух или более одинаковых подряд идущих букв замени этой буквой, за которой следует длина последовательности, а отдельную букву оставь без изменений. Например, aabccc превращается в a2bc3. Верни сжатую строку.

Заглавные и строчные буквы считаются разными: aA — это две последовательности длиной 1.

Функция

compress(s: string) → string

sstring: строка для сжатия, только английские буквы
Возвращаетstring: сжатая строка, каждый повтор записывается как буква и её количество, если количество больше 1

Ограничения

1 ≤ s.length ≤ 2 × 10⁴
s содержит только английские буквы: от a до z и от A до Z.
Длина серии записывается в десятичной системе и может состоять из нескольких цифр.

Примеры

Ввод: s = "aabccc"
Вывод: "a2bc3"
Пояснение: Группы — это aa, b и ccc. Они преобразуются в a2, b (одиночная буква не получает счётчик) и c3.

Ввод: s = "abbbbbbbbbbbb"
Вывод: "ab12"
Пояснение: Одна a, затем двенадцать b. Длина 12 записывается двумя символами 1 и 2, поэтому результат — ab12.

Ввод: s = "zzZZZ"
Вывод: "z2Z3"
Пояснение: Строчная z и заглавная Z — это разные буквы, поэтому здесь сначала идет серия из двух, за которой следует серия из трех: z2Z3.

Дополнительный вопрос

Запишите обратное: имея сжатую строку, например ab12, восстановите исходную. Как прочитать количество, состоящее из нескольких цифр?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Собери запуски, затем запиши их

Идея

Сначала запишите серии в виде пар «буква и длина»: для aabccc — (a, 2), (b, 1), (c, 3). Каждая буква либо продолжает последнюю серию, либо начинает новую. Затем запишите букву каждой серии, а после неё — длину, если она больше 1.

Оба прохода выполняются за O(n). В списке может быть n серий, если никакие две соседние буквы не совпадают, поэтому требуется O(n) дополнительной памяти.

Алгоритм

Создай пустой список серий.
Для каждой буквы в s: если в последней серии та же буква, увеличь её длину на 1; иначе добавь новую серию длиной 1.
Для каждой серии запиши её букву, а затем её длину в виде десятичного числа, если длина больше 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Два указателя для каждого непрерывного фрагмента

Идея

Оставь i на первой букве текущей последовательности и двигай j вперёд, пока s[j] равно s[i]. Когда j остановится — на другой букве или в конце, — длина последовательности равна j-i. Запиши её и присвой i = j. Для abbbbbbbbbbbb j сначала остановится на 1, дав a, затем на 13, дав b12.

Для последней последовательности не нужен отдельный случай, потому что внутренний цикл остановится в конце строки. j движется только вперёд, поэтому время работы составляет O(n), а помимо результата нужно хранить два индекса. В версиях на R и Swift сначала строка s разбивается на массив символов, поэтому они используют O(n) дополнительной памяти.

Алгоритм

Установи i = 0.
Пока i находится внутри строки, установи j = i и продвигай j вперёд, пока он находится внутри строки и s[j] равно s[i].
Запиши s[i]; если j-i больше 1, запиши его в виде десятичного текста.
Установи i = j и повтори.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Ловушки и крайние случаи

Запись серии только при встрече с другой буквой. После последнего ccc в aabccc ничего нет, поэтому вы возвращаете a2b.
Запись количества одним символом, например '0' + count. Это не работает для 10: для двенадцати b нужны два символа 12.
Запись 1 после одиночной буквы. b остаётся b, а не b1.
Игнорирование регистра. zzZZZ — это z2Z3, а не z5.
Наращивание неизменяемой строки с помощью +, как в Java или C#. Каждый + копирует уже полученный результат, из-за чего цикл имеет сложность O(n²); используйте построитель строк.

Частые вопросы3

Какова временная сложность сжатия строки?

Обход двумя указателями занимает O(n) времени, потому что индекс сканирования движется только вперёд. Помимо результата, он хранит два индекса, поэтому дополнительная память составляет O(1).

Может ли сжатая строка быть длиннее исходной?

Не в этой версии. Одна буква остаётся одним символом, а последовательность из k ≥ 2 букв превращается в одну букву и цифры числа k — никогда не более чем в k символов. Схема, в которой количество записывается после каждой буквы, например a1b1, может удвоить длину.

Как сжать строку на месте?

Используй массив символов с индексом чтения и индексом записи. Просматривай каждую группу символов с помощью индекса чтения, затем записывай её букву и цифры её длины по индексу записи. Результат никогда не длиннее уже прочитанной части входных данных, поэтому индекс записи никогда не опережает индекс чтения. В конце верни новую длину.

def compress(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "aabccc"

Ожидаемый вывод

"a2bc3"