Hacker Rank Annagrams

Question

I am trying to solve the problem described here with JavaScript...

https://www.hackerrank.com/challenges/ctci-making-anagrams

I have to output the number of letters that would need to be removed from two strings in order for there to only be matching letters (compare the two strings for matching letters and total the letters that don't match)

for example...

string a = cbe string b = abc

the only matching letter is between both strings is the two c's so I would be removing 4 letters (beab).

My code works, but it seems to keep timing out. If I download the individual test case instances, I seem to fail when variables a and b are set to large strings. If I test these individually, I seem to get the right output but i still also get the message "Terminated due to timeout".

I'm thinking it might be obvious to someone why my code timesout. I'm not sure it's the most elegant way of solving the problem but I'd love to get it working. Any help would be much appreciated...

function main() {
    var a = readLine();
    var b = readLine();

    var arraya = a.split('');
    var arrayb = b.split('');

    var arraylengths = arraya.length + arrayb.length;

    //console.log(arraylengths); 

    if (arraya.length <= arrayb.length) {
        var shortestarray = arraya;
        var longestarray = arrayb;
    } else {
        var shortestarray = arrayb;
        var longestarray = arraya;
    }

    var subtract = 0;

    for (x = 0; x < shortestarray.length; x++) {

        var theletter = shortestarray[x];
        var thenumber = x;

        if (longestarray.indexOf(theletter, 0) > -1) {

            var index = longestarray.indexOf(theletter, 0);

            longestarray.splice(index, 1);

            subtract = subtract + 2;

        }
    }


    var total = arraylengths - subtract;

    console.log(total);
}

your code is timing out _because_ it's not the most elegant way of solving the problem. HackerRank problems, in general, will test your code against very long inputs and impose a fairly short time limit in order to prevent you from using simple but inefficient algorithms like this, and to force you to use "better" ones — Hamms, Jun 01 '17 at 23:23
So what you're saying is trash it and start from scratch? I mean, is any of it any good? — Chris Hopkins, Jun 01 '17 at 23:28
All I'm saying is that it's not the most elegant way of solving the problem; please don't put words in my mouth. To help diagnose which parts of your algorithm could be improved, focus on those parts which execute for every character in the array; in other words, for those parts whose execution time with scale directly with the length of the arrays. — Hamms, Jun 01 '17 at 23:33
Ha Apologies mate. I'm kinda tired. I didn't mean it to come across like that. Ok that makes sense. Thanks for the advice — Chris Hopkins, Jun 01 '17 at 23:40
Debugging can definitely be frustrating; no worries. In particular, you should note that `indexOf` is not a constant-time operation; it's actually searching the whole array every time you call it, and is therefore fairly expensive. — Hamms, Jun 01 '17 at 23:45

Zaid Khan · Answer 1 · 2017-06-02T02:27:44.337

I would suggest you hashing. make the characters of string key and its numbers of occurrences value. Do the same for both strings. After that take string 1 and match the count of its every character with the count of same character in string then calculate the difference in the number of occurrences of the same character and delete that character till the difference becomes 0 and count that how many times you performed delete operation.

ALGORITHM:

step 1: Let arr1[255]= an integer array for storing the count of string1[i]
        and initialized to zero

        ex: string1[i]='a',  then arr1[97]=1, because ASCII value of a is 97  
        and its count is 1. so we made hash table for arr1 where key is 
        ASCII value of character and value is its no of occurrences.

step 2: Now declare an another array of same type and same size for string 2

step 3: For i=0 to length(string1):
               do arr1[string1[i]]++;
step 4: For i=0 to length(string2):
               do arr2[string2[i]]++;

step 5: Declare an boolean char_status[255] array to check if the 
        character is visited or not during traversing and initialize it to 
        false

step 6: set count=0;

step 7: For i=0 to length(string1):
              if(char_status[string1[i]]==false):
                    count=count+abs(arr1[string1[i]]-arr2[string1[i]])
                    char_status[string1[i]]=true

step 8: For i=0 to length(string2):
             if(char_status[string2[i]]==false):
                     count=count+abs(arr1[string2[i]]-arr2[string2[i]])
                     char_status[string2[i]]=true

step 9: print count

I have applied this algo just now and passed all test cases. You may improve this algo more if you have time.

This is something for me to study. I'd like to be versatile enough to have many different ways to approaching problems so thanks very much for your input. :) — Chris Hopkins, Jun 03 '17 at 10:20

karthick · Accepted Answer · 2017-06-02T07:40:28.323

Your algorithm is good. It's straight forward and easy to understand. There are certain things you can do to improve the performance of your code.

You don't have to calculate the indexOf operation twice. you can reduce it to one.
the splice operation is the costliest operation because the JS engine has to delete the element from an array and reassign the indexes of all the elements. A point to be noted here is that the JS engine does an extra step of correcting the index of the array, which is not required for your purpose. So you can safely remove longestarray.splice(index, 1); and replace it with delete longestarray[index]

Here is a snippet which will increase your performance of the code without changing your logic

for (var x = 0; x < shortestarray.length; x++) {
    var theletter = shortestarray[x];    
    var thenumber = longestarray.indexOf(theletter, 0);   // <-- check only once 
    if (thenumber > -1) {
        var index = thenumber;
        delete longestarray[index]; // <-- less costlier than splice
        subtract = subtract + 2;
    }
}

Note: I am not suggesting you to use delete for all the cases. It's useful here because you are not going to do much with the array elements after the element is deleted.

All the best. Happy Coding

Hi Chris if the solution is correct and helped you. Kindly mark it as answer — karthick, Jun 03 '17 at 12:48

Hacker Rank Annagrams

2 Answers2