Checking whether one string contains all the characters of another string

Question

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 < 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");

Answer 1

function scramble(world, seed) {
    var arr = new Array(256);
    var i = 0;
    
    for (i = 0; i < 256; i++) {
      arr[i] = 0;
    }
    
    for (i = 0; i < world.length; i++) {
      arr[world.charCodeAt(i)] += 1;
    }
    
    for (i = 0; i < seed.length; i++) {
      arr[seed.charCodeAt(i)] -= 1;
      if (arr[seed.charCodeAt(i)] < 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 < world.length; i++) {
      arr[world[i]] = (arr[world[i]] || 0) + 1;
    }

    for (i = 0; i < seed.length; i++) {
      arr[seed[i]] = (arr[seed[i]] || 0 ) - 1;
      if (arr[seed[i]] < 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.

Answer 2

Your algorithm is \$O(n^2)\$ because you're searching and copying str1 each time through the loop. In general, when you need to do repeated searches, you can optimize by turning the searched array/string into an object whose keys are what you're searching for.

However, in this task you also need to deal with repeated copies of the same character; if a characters is repeated in the second string, it has to have at least as many copies in the first string. You can handle this by putting the repetition count into the values of the object. When searching, decrement the count every time a match is found. The test if (obj1[c]) will fail if either the character isn't found or its count has decremented to 0. Use post-decrement on this so you test the value before the decrement.

function scramble(str1, str2) {
  const obj1 = {};
  str1.split('').forEach(c => obj1[c] = (obj1[c] || 0) + 1);
  return str2.split('').every(c => obj1[c]--);
}

console.log(scramble('rkqodlw','world'), "should be true");
console.log(scramble('cedewaraaossoqqyt','codewars'), "should be true");
console.log(scramble('katas','steak'), "should be false");
console.log(scramble('scriptjava','javascript'), "should be true");
console.log(scramble('scriptingjava','javascript'), "should be true");
console.log(scramble('javscripts','javascript'), "should be false");
console.log(scramble('aabbcamaomsccdd','commas'), "should be true");

Answer 3

I just made a slighty different variant with every and includes, jsperf says that there's a litte bit difference on performance (the code below is 'apparently' fastest).

Also as @wOxxOm says you're modifying a global variable in your for loop, don't forget to add the missing var keyword to the initialization part of the for loop (var i).

function scramble(string1, string2) {
  return string2.split('').every(function(character) {
    // Every string2 characters must be included in the string1
    return string1.includes(character);
  });
}

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

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

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

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

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

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

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

One disadvantage of this way is that the string.includes method is not supported by internet explorer, besides some versions of firefox (18-48) previously called this method as contains, so be careful with that.

Answer 4

finding and replacing can get costly... Since you need only to find characters, you might prefer removing the need to replace!

for(i = 0; i < str2Length; i++){ 
        if(str1.indexOf(str2[i])==-1){
            return false;
        }       
}

This has 2 benefits: We don't need to find ALL occurrences of a character, just one is enough to determine what we are looking for. And since we only want to know if the characters are in the string, we don't change the value of anything giving us another little speed increase.

My .02 about your code:

Although you are aiming for speed, it would be wise to use variable names that would mean something. Instead of str1 and str2, it could be haystack and needle or subject and search... I'm not sure if the function name is yours to choose but there too I would change the name, this function does not scramble anything.