Определение, можно ли собрать одну строку из символов другой

Условие

Необходимо реализовать функцию scramble(source, target), которая возвращает true, если из символов строки source можно собрать строку target путём их перестановки. Если собрать target невозможно, функция должна вернуть false. Примеры:

scramble('scriptingjava', 'javascript') => true
scramble('abc', 'a') => true
scramble('abc', 'd') => false

Ответ

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

function scramble(source, target) {
  const counts = new Map();
  for (const char of source) counts.set(char, (counts.get(char) ?? 0) + 1);
  for (const char of target) {
    const count = counts.get(char) ?? 0;
    if (count === 0) return false;
    counts.set(char, count - 1);
  }
  return true;
}

Одного Set недостаточно: он не учитывает повторения букв. Пустую target можно собрать всегда, лишние символы source не мешают. Сравнение чувствительно к регистру; правила нормализации условием не заданы. Время O(n + m), память O(k) для различных символов source.