4
\$\begingroup\$

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");
\$\endgroup\$
  • \$\begingroup\$ You have a bug: i is global (missing var) so if the perf code uses i too you cause an infinite loop. \$\endgroup\$ – wOxxOm Oct 29 '17 at 22:26
  • \$\begingroup\$ Thank you for pointing that out, wOxxOm. I have done some searching and found out why it is important. \$\endgroup\$ – user109140 Oct 30 '17 at 14:55
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I never would have thought of approaching this by using that ASCII approach. I will definitely look into your examples. \$\endgroup\$ – user109140 Oct 30 '17 at 17:00
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. I will look into this one. I am almost certain that the CodeWars servers that run the final tests are using Chrome browsers. I had an issue before with a kata that uses the array sort method. There is some variation of the array sort method works differently with Chrome compared to other browsers. \$\endgroup\$ – user109140 Oct 30 '17 at 13:50
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I agree 100% about the variable names. They are given as part of the kata description. I sometimes change them when the code is longer and I need better/more descriptive names. \$\endgroup\$ – user109140 Oct 30 '17 at 13:40
  • \$\begingroup\$ I need to use replace with nothing and put the value back into str1 to repeat the search. If there are two of a character like the last test case, I need to find/replace the first "m", and then find the second: 'aabbcamaomsccdd','commas' \$\endgroup\$ – user109140 Oct 30 '17 at 13:46
  • \$\begingroup\$ That is one gotcha that wasn't explicit at all... Then you are right, my solution cannot solve the problem alone. \$\endgroup\$ – Salketer Oct 30 '17 at 14:17
0
\$\begingroup\$

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.

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

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

\$\endgroup\$
  • \$\begingroup\$ Thank you, Barmar. I will look at this and hopefully learn from it. I do need to learn how to use JavaScript objects more. I only use them for very simple things. \$\endgroup\$ – user109140 Nov 5 '17 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy