Сжатие строки

Постановка задачи

chars = ["a", "a", "b", "b", "c", "c", "c"]

6

["a", "2", "b", "2", "c", "3"]

chars = ["a"]

1

["a"]

chars = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"]

4

["a", "b", "1", "2"]

Решение

Эта задача проверяет умение аккуратно менять массив "на месте". На первый взгляд может показаться, что проще всего создать новую строку или новый массив, собрать туда ответ и вернуть его длину. Но по условию нужно записать результат прямо в исходный массив chars.

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

Идея решения:

Будем использовать два указателя:

• r - текущая позиция чтения в исходном массиве
• w - позиция, куда нужно записать следующий символ сжатого результата

Пока r не дошел до конца массива, мы берем текущий символ и считаем длину его группы. Например, для группы ["c", "c", "c"] символ будет "c", а длина группы будет 3.

После этого записываем символ в позицию w. Если длина группы больше 1, записываем цифры количества повторений сразу после символа. Затем переходим к следующей группе.

Почему это безопасно делать на месте? Сжатая запись каждой группы короче или равна исходной группе:

• группа длины 1 записывается как один символ
• группа длины от 2 до 9 записывается как два символа
• группа длины 10 и больше записывается как символ и несколько цифр, но это все равно короче или равно исходной группе

Поэтому w не обгонит r и не затрет необработанные данные.

Основные шаги:

1. Инициализация: ставим r = 0 и w = 0.

2. Обрабатываем очередную группу одинаковых символов.

   • Запоминаем текущий символ chars[r].
   • Считаем, сколько раз он идет подряд.
   • После подсчета r уже указывает на начало следующей группы.

3. Записываем сжатое представление.

   • Сначала записываем сам символ в chars[w].
   • Если количество повторений больше 1, записываем каждую цифру счетчика отдельным символом.

4. Завершение цикла:

   • Когда r дошел до конца массива, w указывает на длину сжатого результата.
   • Возвращаем w.

Разберем пример:

chars = ["a", "a", "b", "b", "c", "c", "c"]

1. Первая группа - символ "a".

   • Символ "a" повторяется два раза.
   • Записываем "a" и "2".
   • Массив: ["a", "2", ...], w = 2.

2. Вторая группа - символ "b".

   • Символ "b" повторяется два раза.
   • Записываем "b" и "2".
   • Массив: ["a", "2", "b", "2", ...], w = 4.

3. Третья группа - символ "c".

   • Символ "c" повторяется три раза.
   • Записываем "c" и "3".
   • Массив: ["a", "2", "b", "2", "c", "3", ...], w = 6.

Итог: возвращаем 6. Первые шесть элементов массива содержат правильный ответ: ["a", "2", "b", "2", "c", "3"].

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

Временная сложность

Мы проходим по массиву один раз. Каждый символ читается ровно один раз, а запись количества повторений добавляет только цифры ответа.

Таким образом, временная сложность равна O(n), где n - длина массива chars.

Пространственная сложность

Мы меняем исходный массив и используем только несколько переменных. Строковое представление счетчика можно считать константным для ограничений задачи, поэтому пространственная сложность равна O(1).

Код решения

Приведем код решения.

func compress(chars []byte) int {
    w := 0
    r := 0
    for r < len(chars) {
        c := chars[r]
        count := 0
        for r < len(chars) && chars[r] == c {
            r++
            count++
        }
 
        chars[w] = c
        w++
        if count > 1 {
            for _, digit := range strconv.Itoa(count) {
                chars[w] = byte(digit)
                w++
            }
        }
    }
    return w
 
}
 

Итоги

Вот основные итоги по задаче:

1. Два указателя разделяют чтение и запись. r идет по исходному массиву, а w формирует сжатый префикс.

2. Группа обрабатывается целиком. Сначала считаем длину группы одинаковых символов, затем записываем символ и количество.

3. Одиночные символы не получают счетчик. Группа длины 1 остается одним символом.

4. Многозначный счетчик пишется по цифрам. Число 12 должно стать символами "1" и "2", а не одним значением.