Checking whether one string matches another

Question

This checks whether one string has all the chars in another string to make up that exact string. Counts matter so for, for example, str1 = 'abcdgbff' str2 ='aaabb' should return false because str1 only has one 'a' and 'b'.

How can I optimize my code further?

function scramble(str1, str2) {
  for (let i of str1) {
    if (str2.indexOf(i) != -1) {
      str2 = str2.slice(0, (str2.indexOf(i))) + str2.slice(str2.indexOf(i) + 1);
    }
  }
  return str2.length === 0;
}

// Example:
console.log(scramble('abcdgbff', 'aaabb')); // false

Answer 1

If your input strings are of length n, your current implementation has a cubic runtime complexity O(n³). This could become an issue for longer strings.

I recommend to split counting character frequencies and comparing those counts into two separate steps with nearly linear complexity O(n):

// Count characters in 'str':
function frequencies(str) {
  let result = {};
  for (let chr of str) {
    result[chr] = (result[chr] || 0) + 1;
  }
  return result;
}

// Check if 'str1' contains all characters of 'str2':
function scramble(str1, str2) {
  let frequencies1 = frequencies(str1);
  let frequencies2 = frequencies(str2);
  return Object.entries(frequencies2).every(([chr2, frequency2]) =>
    frequencies1[chr2] >= frequency2
  );
}

// Examples:
console.log(scramble("abc", "cba"));
console.log(scramble("aa", "aaaa"));
console.log(scramble("123", "234"));

Answer 2

I can't program in JavaScript but i will tell you, your dealing with strings, so if you look at the type of input and know that the third letter into a word is usualy a vowl, but the last is usually a consent, then you can try to make your code error/False statement as fast as possible, if you choose to measure length then chose Consent positions to compare first.