Пишем функцию RLE для компрессии строки

В этом уроке мы рассмотрим решение задачи по компрессии строки с помощью кодирования повторов. Такое кодирование называется RLE (Run-length encoding). Сутью алгоритма является замена повторяющихся символов цифрой, обозначающей количество повторов. Кодирование чаще всего применяется для данных, которые содержат большое количество серий одинаковых символов, например, иконки и графические рисунки.

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

Условия задачи

Дана строка, состоящая из букв A-Z: 'AAAABBBCCXYZDDDDEEEFFFAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB'

Нужно написать функцию, которая:

• на выходе вернет строку вида 'A4B3C2XYZD4E3F3A6B28'
• сгенерирует любую ошибку, если на вход пришла невалидная строка

Дополнительные пояснения:

• eсли символ встречается 1 раз, он остается без изменений
• если символ повторяется более 1 раза, к нему добавляется количество повторений

function rle(str) {
  // your code 
}

Подготовка

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

console.log(rle('AAAABBBCCXYZDDDDEEEFFFAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB')) // 'A4B3C2XYZD4E3F3A6B28'
console.log(rle('ABC')) // 'ABC'
console.log(rle('')) // ''
console.log(rle('A4B3C2XYZD4E3F3A6B28')) // Error

На этом этапе также стоит обдумать пути решения задачи и предположить ожидаемую алгоритмическую сложность. Мы будем писать решение с линейной алгоритмической сложностью O(n), то есть скорость выполнения будет напрямую зависеть от длины строки.

Решим задачу путем последовательного перебора символов и использования указателей для хранения текущего состояния перебора. Понадобится 3 указателя для хранения промежуточного результата, текущей буквы и количества повторов.

Решение

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

function rle(str) {
  if (str === "") return str;

  if (!str.match(/^[A-Z]+$/)) {
    throw new Error(`'${str}' is invalid input for rle()`);
  }

  // ...
}

Объявим переменные-указатели для хранения промежуточного состояния с начальными значениями. Для получения символа можно использовать метод charAt. Он повышает читаемость кода, указывая на то, что в переменной строка. Этот метод работает даже в IE7, в отличие от обращения по индексу. Однако, обращение по индексу str[index] тоже ипользуется повсеместно.

function rle(str) {
  // ...

  let result = "",
    current = str.charAt(0),
    count = 1;
     
  // ...
}

Линейно итерируем по строке, начиная со второго символа. Первый у нас уже выбран как текущий. Сравниваем текущий символ с символом из итерации. Если они разные, записываем текущий символ в финальную строку. При наличии более одного повтора добавляем к символу количество повторов. Если символы совпадают, итерируем дальше и увеличиваем счетчик повторов.

function rle(str) {
  // ...

  for (let i = 1; i < str.length; i++) {
    if (str.charAt(i) !== current) {
      result += current;
      if (count > 1) {
        result += count;
        count = 1;
      }
      current = str.charAt(i);
    } else {
      count++;
    }
  }

  // ...
}

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

function rle(str) {
  if (str === "") return str;

  if (!str.match(/^[A-Z]+$/)) {
    throw new Error(`'${str}' is invalid input for rle()`);
  }

  let result = "",
    current = str.charAt(0),
    count = 1;

  for (let i = 1; i < str.length; i++) {
    if (str.charAt(i) !== current) {
      result += current;
      if (count > 1) {
        result += count;
        count = 1;
      }
      current = str.charAt(i);
    } else {
      count++;
    }
  }

  result += current;

  return result;
}

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

Проработка

Решите задачу, пройдя все подготовленные тесты.