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

Question

Простейший алгоритм сжатия строки — это run-length encoding, при котором одинаковые символы заменяются символом и количеством повторений. Например, aaabb превращается в a3b2. Такой алгоритм выполняется за O(n), так как строка проходит один раз.

YeaHub · Accepted Answer

Один из самых простых способов сжатия строки — алгоритм 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 — простой алгоритм сжатия, который удобен для задач с повторяющимися символами и хорошо демонстрирует оценку сложности.