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

Один из самых простых способов сжатия строки — алгоритм RLE (Run-Length Encoding).

Идея алгоритма

Определение:
RLE — это метод сжатия, при котором последовательности одинаковых символов заменяются символом и количеством повторений.

Пример

aaabcccc → a3b1c4

Пример реализации

function compress(str) {
  let result = "";
  let count = 1;

  for (let i = 1; i <= str.length; i++) {
    if (str[i] === str[i - 1]) {
      count++;
    } else {
      result += str[i - 1] + count;
      count = 1;
    }
  }
  return result;
}

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

• Временная сложность: O(n)

• Пространственная сложность: O(n)

Причина:

• строка проходит один раз

• результат хранится отдельно

Где применяется

• простые форматы сжатия

• кодирование данных

• обработка логов

Вывод

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