4
\$\begingroup\$
function scramble(str1,str2) {
  let result;
  for(let i = 0; i < str2.length; i++){

    let found = str1.match(new RegExp(str2.charAt(i)));

    if(found === null){
      result = false;
      break;
    } else {
      str1 = str1.replace(found, "");
      result = true;
    }
  }

  return result;
}

The purpose of this function is to verify if the letters of the second string are contained in the first string and can be rescrambled to create the the word:

scramble('rkqodlw', 'world'); //true
scramble("scriptjavx", "javascript"); //false
scramble('katas', 'steak'); //false

The above is working but I am looking to improve the performance time to less than 12000ms for for any given string.

\$\endgroup\$
6
  • \$\begingroup\$ Why is scramble("scriptjavx", "javascript"); //false? Letters can be used only once? \$\endgroup\$ Commented Dec 2, 2018 at 3:57
  • \$\begingroup\$ yes, letters can only be used once because they have to be able to be rearranged to create input string \$\endgroup\$
    – Roscoe
    Commented Dec 2, 2018 at 3:59
  • \$\begingroup\$ How is testing performed to derive "less than 12000ms"? \$\endgroup\$ Commented Dec 2, 2018 at 4:02
  • \$\begingroup\$ What are the test cases for "any given string"? \$\endgroup\$ Commented Dec 2, 2018 at 4:30
  • \$\begingroup\$ This is a codewars challenge and eventhough all my test pass. It says the execution timed out: Execution Timed Out (12000 ms) \$\endgroup\$
    – Roscoe
    Commented Dec 2, 2018 at 6:29

1 Answer 1

1
\$\begingroup\$

12 seconds

is forever for a CPU. However your solutions is so complex, 12 seconds is likely it timing out on a string that is only a few K long.

These code sites also like to throw curve balls, passing arguments that have very quick solutions if you check for them, but if you don't will take so long it will time you out.

Also know that these sites run distributed virtual machines on which they test code, some (all that I tested) time how long it takes to get a result not how long your code takes to run. If its busy that time will include how long it takes to locate CPU/Memory resource (VM), setup context (Javascript runtime), and then execute your code. So times vary and should never be used as an indication of performance.

Performant and Complexity

The first step to fast solutions is always write performant code,

Basic performant optimisations

  1. Locate opportunities to exit early. In this case, is the first string is shorter than the second then you know the result must be false.

  2. Locate lines of code that are repeated in iteration that can be done once. In this case you set result to true each time you find a match. You need only do it once by assigning true to result when you declare it.

  3. Avoid redundancy. Redundant lines of code take time to execute. In this case result is not needed as you can return the result directly from within the statement found===null, removing the need for break, and defining result.

  4. Develop a good Understanding of available language features and stay up to date. MDN has a good Javascript reference. Knowing this reference in your head will makes your code faster, to know it in your head means you must continuously be studying the reference as JavaScript is always changing.

    String.match is not the only way to test for a character. Also it can return an array which is less performant than a bool such as RegExp.test, and String.includes or a Number such as String.indexOf.

    Once a year read the Javascript Spec (current ECMAScript2019) Its long and dry, not an easy read for beginners (or 40+ year vets) , so read it again, and again. This will not only reenforce your internal mind javascript reference but give you an understanding of how javascript does what it does. (Help you understand JS complexity. See below)

    Test your understanding. Is str1 === str2 faster than str1.length === str2.length ? If you dont know write some code to find out.

A more performant solution

From that you can get a good improvement in overall performance. An example follows

function scramble(str1,str2) {
    var i;
    if (str1.length >= str2.length) {
        if (str1 === str2) { return true }
        for (i = 0; i < str2.length; i++) {
            const str = str1.replace(str2[i]);
            if (str.length === str1.length) { return false }
            str1 = str;
        }
        return true;
    }
    return false;
}

That may pass the time limit but as the size of the strings grows the improvement in performance reduces.

For 2 char strings this a twice as fast. When str1 is shorter than str2 this is a above umteenQuadBillion times faster. If str1 is longer or equal len to str2 then for a 4K string it will likely timeout, taking only a few ms shorter to solve.


Complexity

In computer science there is a difference between performance and complexity. The above code has better performance and hence will always be a little quicker, however it has the same complexity and thus not going to help you.

The metric n

We measure an algorithm's complexity in terms of some metric. In this case the metric can be the mean size of both strings. We call it n and use that to create a formula that counts the number operations per n needed to complete the task.

For example count A's in a string

// Note len is string len
count = 0                   
for(i = 0; i < len; i++){ 
    if(str[i] === "A") { 
        count ++ 
    } 
    
}
  • 2 operations to set count and start the loop.

  • 1 op for the loop.

  • 1 op for the test.

  • if there is an "A" 1 op to count.

    We can say that the complexity has a worst (all A's) case of 2 + 3 * n complexity and a best case (No A's) of 2 + 2 * n

The difference between best a worst case can be huge, generally we define what the complexity is for (worst, mean, or best case). Without that we assume the complexity is the worst case

Big O notation.

Formalized we call the expression of complexity big O notation and you will see it as a math function, sometimes O(2 + 3 * n) but most often just the n or a number O(n), O(n2) or O(1).

Complexity grows quickly

Lets up the complexity and count the number of chars in str1 that exist in str2

count = 0                   
for(i = 0; i < len1; i++){ 
    for(j = 0; j < len2; j++){ 
        if(str1[i] === str2[j]) { 
            count ++ 
        } 
    }
}

Now n is the mean string len and there are

  • 2 ops to get into the first loop,
  • for each n there is
    • 1 op to loop and another to enter the inner loop. thus 2 * n.
    • then for each inner loop
      • 1 to loop, and 2 to count.

The complexity is O(2 + 2 * n + 3 * n * n)

Note that the there is a n * n or we can express it as n^2 or n2 thus O(2 + 2n + 3n2)

The highest power

The function inside the () is called a polynomial.

There is a property of polynomials that allow for simplification.

As the value of n grows the size of the term that has the highest power n2 gets so large that the other terms (2 + 2n + 3 * ) become insignificant.

With this in mind Big O ignore all but the highest power. So for the above the complexity is not O(2 + 2n + 3n2) but O(n2)

Javascript complexity.

As part of understanding javascript you need to know the complexity of the many javascript functions and operators.

Some examples

if(a === b)  // if numbers O(1)
if(a === b)  // if strings O(n) where n is string len (it may be a little lower (O(n<sup>logn</sup>)
if(a.includes(b)) // if a is array of numbers b is a number O(n) n is size of array
if(a.includes(b)) // if a is array of string b is a string the worst case O(n**2)

So a single JS line can not just be counted as a single operations, each line can have vastly different complexity

So looking at your code the outer loop is O(n) but inside we have str1.match and str1.replace both of which are O(n). So overall its O(n2). The same for the more performant version I wrote. The str1.replace is O(n) thus the solution is O(n2)

Optimise complexity target the highest big O power

So if we can reduce the size of the highest power in a solution, even if that means more code we can get huge improvements in complexity.

One solution is to go over the first string and count the number of times each letter occurs, storing the count in an array, one item for each possible character. Then go over the second array and for each subtract 1 from the counts. If any of the counts are negative we know that the first string is missing a value that is in the second.

function scramble(str1,str2) {
    const buf = new Uint8Array(256);
    var i = 0;
    if (str1.length >= str2.length) {
        if (str1 === str2) { return true }
        while(i < str1.length) {
            buf[str1.charCodeAt(i++)] ++;
        }
        i = 0;
        while(i < str2.length) {
            const idx = str2.charCodeAt(i++);
            if(buf[idx] === 0) { return false }
            buf[idx] --;
        }
        return true;
    }
    return false;
}

If we write out the full complexity its 256 + 3 + 2n + 1 + 4n + 1 or 261 + 6n the 256 is to create and fill the array with zeros. If the strings are unicode it would be 65536 + 5 + 5n

But only the highest power matters so the above function is O(n)

Now if the strings are the same size and the mean length is 4000 this solution should be around 4000 times faster.

Caveats

There are however some caveats for the above solution

The array holding the counts must be able to count all the characters.

To ensure the function will work use an array of 32bit unsigned ints which will handle strings upto 4Gb is size. If the function errors the strings may be unicode and thus you will need to use a larger array 65536 items long.

The O(n) solution.

function scramble(str1, str2) {
    const buf = new Uint32Array(256);  // For unicode array size is 65536
    var i = 0;
    if (str1.length >= str2.length) {
        if (str1 === str2) { return true }
        while (i < str1.length) {
            buf[str1.charCodeAt(i++)] ++;
        }
        i = 0;
        while (i < str2.length) {
            const idx = str2.charCodeAt(i++);
            if (buf[idx] === 0) { return false }
            buf[idx] --;
        }
        return true;
    }
    return false;
}

    
\$\endgroup\$
8
  • 2
    \$\begingroup\$ So overall its O(n2)”- should that have been ”So overall its O(n<sup>2</sup>)”? \$\endgroup\$ Commented Dec 3, 2018 at 5:31
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ Thanks, it was a long post and I missed the backslash in closing sup \$\endgroup\$
    – Blindman67
    Commented Dec 3, 2018 at 5:45
  • 1
    \$\begingroup\$ Why not simply use a HashMap in place of array and forget about the alphabet size and, perhaps, save some memory? \$\endgroup\$
    – bipll
    Commented Dec 3, 2018 at 5:48
  • 1
    \$\begingroup\$ @Blindman67 By 'O(1)', do you mean 'O(65536)'? \$\endgroup\$
    – bipll
    Commented Dec 3, 2018 at 6:31
  • 1
    \$\begingroup\$ @bipll No I mean O(1). We write the highest power only, thus O(65536 * n ^ 0) is written as O(1) \$\endgroup\$
    – Blindman67
    Commented Dec 3, 2018 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.