Checking whether one string contains all the characters of another string I am working on a CodeWars kata that requires the code to run under a certain time limit. This code passes all the tests; but, it doesn't run fast enough. I don't know what else I can trim down or change. 

Addition: I tried looking up a String.split-join solution. But, that won't work. The split will replace every occurrence of a character. I need to check for only one at a time. I even tried using the split-join with RegEx that only took one occurrence of a character. But, that was just adding more code on top of what I already had. 

Putting the strings into arrays is too slow.

Someone suggested that I try a different way of looking at the problem by rearranging the characters. Maybe I need to sort them which will group the duplicate characters together. 



Kata description:


  If all the characters in the second string are found in the first string, then return true; otherwise, return false.


I included some test cases at the end.

function scramble(str1, str2) {

var str2Length = str2.length;
var str11 = "";

for(i = 0; i &lt; str2Length; i++){ 
        str11 = str1.replace(str2[i], '');
        if(str11 === str1){
            return false;
        }       
        str1 = str11;
}
// If all the characters have been found in the second string, then return true.
    return true;


}

scramble('rkqodlw','world');
console.log("should be true");

scramble('cedewaraaossoqqyt','codewars');
console.log("should be true");

scramble('katas','steak');
console.log("should be false");

scramble('scriptjava','javascript');
console.log("should be true");

scramble('scriptingjava','javascript');
console.log("should be true");

scramble('jscripts','javascript'); 
console.log("should be false");

scramble('aabbcamaomsccdd','commas');
console.log("should be true");
function scramble(world, seed) {
    var arr = new Array(256);
    var i = 0;
    
    for (i = 0; i &lt; 256; i++) {
      arr[i] = 0;
    }
    
    for (i = 0; i &lt; world.length; i++) {
      arr[world.charCodeAt(i)] += 1;
    }
    
    for (i = 0; i &lt; seed.length; i++) {
      arr[seed.charCodeAt(i)] -= 1;
      if (arr[seed.charCodeAt(i)] &lt; 0) {
        return false;
      }
    }
    
    return true;
}

console.log(scramble('rkqodlw','world'));
console.log("should be true");

console.log(scramble('cedewaraaossoqqyt','codewars'));
console.log("should be true");

console.log(scramble('katas','steak'));
console.log("should be false");

console.log(scramble('scriptjava','javascript'));
console.log("should be true");

console.log(scramble('scriptingjava','javascript'));
console.log("should be true");

console.log(scramble('jscripts','javascript')); 
console.log("should be false");

console.log(scramble('aabbcamaomsccdd','commas'));
console.log("should be true");




Pretty sure it's much faster. As for why, it's about complexity. First a loop of 256 iterations (so nothing), then a loop O(n), then another O(n) loop, where n is the length of either string.

Your code is O(n*n): a loop on the string's length, then the .replace call which is also O(n).

Explanation of the code

Each letter is an ASCII character. ASCII characters have a number representation from 1 to 128 (in the code 256 to be safe).

So I create an array of 256 values, filling it with zeros. Then I count the letters in the first string: increasing the count for the corresponding letter by one. I get the number representation of the letter with .charCodeAt.

Then, for the second string, I decrease the count of each letter by 1 as I encounter the characters. If I end up with a negative number, it means there was more of said letter in the second string than in the first string, and I return false.

The end result is a much faster algorithm.

To be fair, anyone doing C or C++ would come up with this solution. 

Another solution

Another solution, less efficient but still meeting the speed criterion I assume, using objects:

function scramble(world, seed) {
    var obj = {};
    var i = 0;

    for (i = 0; i &lt; world.length; i++) {
      arr[world[i]] = (arr[world[i]] || 0) + 1;
    }

    for (i = 0; i &lt; seed.length; i++) {
      arr[seed[i]] = (arr[seed[i]] || 0 ) - 1;
      if (arr[seed[i]] &lt; 0) {
        return false;
      }
    }

    return true;
}


It's another way of doing things even if you don't know the concept of number representation for letters.