Hackerrank.com - Sherlock and Anagrams Summary: Given a string find the number of anagramic pairs of substrings of it. e.g 'abba' pairs are [a,a],[b,b],[ab,ba],[abb,bba] so we have 4 pairs.

I'm wondering if anyone can help me improve my code so that it runs faster. My code passes all test cases when running locally, but times out on hackerrank. Any ideas ?

module.exports = (s = '') =&gt; {
    let count = 0
    let pairs = []
    for (let wordSize = 1; wordSize &lt; s.length; wordSize++) {
        for (let wordPosition = 0; wordPosition &lt; s.length; wordPosition++) {
            const letters = s.substr(wordPosition, wordSize)
            const wordKeys = letters.split('');
            pairs.push({ letters, keys: wordKeys, wordPosition })
        }
    }
    let pairIndexes = {}
    for (let i = 0; i &lt; pairs.length; i++) {
        const word = pairs[i]
        pairs.forEach((value, index) =&gt; {
            if (word.wordPosition !== value.wordPosition &amp;&amp; index !== i &amp;&amp; value.keys.length === word.keys.length) {
                const wordSorted = word.keys.sort().join('')
                const valueSorted = value.keys.sort().join('')

                if (wordSorted !== valueSorted) return
                if (pairIndexes[wordSorted] === undefined) pairIndexes[wordSorted] = {}
                const pairKeyWord = `${word.wordPosition}-${value.wordPosition}`
                const pairValueWord = `${value.wordPosition}-${word.wordPosition}`
                if (pairIndexes[wordSorted][pairValueWord] === pairKeyWord) return
                pairIndexes[wordSorted][pairKeyWord] = pairValueWord
            }
        })
    }
    //console.log(pairs)
    //console.log(pairIndexes)
    for (const key in pairIndexes) {
        if (pairIndexes.hasOwnProperty(key)) {
            const pairs = pairIndexes[key];
            count += Object.keys(pairs).length
        }
    }
    return count
}


Test cases:

test('A - Given a string return pairs of anagrams', () =&gt; {
  const s = 'mom'
  const expected = 2
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('B - Given a string return pairs of anagrams', () =&gt; {
  const s = 'abba'
  const expected = 4
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('C - Given a string return pairs of anagrams', () =&gt; {
  const s = 'abcd'
  const expected = 0
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('D - Given a string return pairs of anagrams', () =&gt; {
  const s = 'ifailuhkqq'
  const expected = 3
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('E - Given a string return pairs of anagrams', () =&gt; {
  const s = 'kkkk'
  const expected = 10
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('F - Given a string return pairs of anagrams', () =&gt; {
  const s = 'cdcd' // c,c d,d cd,cd, cd,dc dc,cd
  const expected = 5
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('G - Given a string return pairs of anagrams', () =&gt; {
  const s = 'ifailuhkqqhucpoltgtyovarjsnrbfpvmupwjjjfiwwhrlkpekxxnebfrwibylcvkfealgonjkzwlyfhhkefuvgndgdnbelgruel'
  const expected = 399
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('H - Given a string return pairs of anagrams', () =&gt; {
  const s = 'gffryqktmwocejbxfidpjfgrrkpowoxwggxaknmltjcpazgtnakcfcogzatyskqjyorcftwxjrtgayvllutrjxpbzggjxbmxpnde'
  const expected = 471
  const result = anagrams(s)
  expect(result).toBe(expected)
})
Your code does indeed run forever. Regrettably you don't describe the method you're using, so I will have to get that from your code.


You start by getting all possible substring, of all possible sizes, out of the given input string and you store those substrings, its letters and position in an array.
You do a full matrix comparison of each array entry. You test if something is an anagram or not. If it is you store it in a second array.
You count what you stored in the second array.


Somewhere along the way you lost me there. Why all the complexity? You started out well, by getting all possible substrings, but after that it became somewhat messy. A full matrix comparison is certainly not needed. I'll explain.

What are we trying to accomplish here? Let's analyse the problem, taking the simply case of 'abba'. The possible substrings are 'a','b','b','a', 'ab','bb','ba' and 'abb','bba'. nine in total, let's number them 1 to 9. 

A full matrix comparison would make 9 x 9 = 81 comparisons. But it is obvious that this would compare the same substrings twice. Comparing 2 to 5 is the same as comparing 5 to 2. So we can leave out at least half of these comparisons, cutting the time we need to do this in half. We also don't need to compare two strings of unequal length, so we won't. 

So, in the case of 'abba' we have 3 sets we need to compare. For the 1 character set we have to do 6 comparisons, for the 2 character set 3, and for 3 character set 1. That's a total of 10 comparisons where you did 81. This number gets proportionally lower when the size of the input string increases. It is here where we can gain most of our speed.

Finally we get to the comparison itself. Suppose we want to compare 'ab' to 'ba'. By sorting the characters in both strings we can simply compare them. If they are equal that the strings must be an anagram, and must be counted. This is what you do as well.

So now we know what we will need: We need all possible sorted substrings and perform only the needed comparisons.

In basic Javascript code that would look like this:

function sherlockAndAnagrams(s) {
    var anagrams = 0;
    for (var len = 1; len &lt; s.length; len++) {
        var parts = [];
        for (var pos = 0; pos &lt;= s.length - len; pos++) {
            var part = s.substr(pos, len);
            parts.push(part.split('').sort().join(''));
        }
        for (var index1 = 0; index1 &lt; parts.length; index1++) {
            var part1 = parts[index1];
            for (var index2 = index1 + 1; index2 &lt; parts.length; index2++) {
                var part2 = parts[index2];
                if (part1 == part2) anagrams++;
            }
        }
    }
    return anagrams;
}


Notice how the outer loop goes through all the possible lengths of the substring. By working with one length of string, each time, I will never have to compare two differently sized strings.

The way I build the initial array with substrings looks very similar to what you have, but I only store the sorted substrings. That's all that is needed. By sorting the characters in the substring at this stage I save time.

The comparison of the substrings of one length is now quite simple. Notice how index2 starts at index1 + 1, preventing a full matrix comparison of the subset.

And that's it.

So, the major lesson here is to try to reduce the number of comparisons you have to make by first carefully analysing the problem. For an input string of 4 characters you did 81 comparisons, I do 10 (12%). If the input is 16 characters long this goes to 18,225 and 680 (4%), 32 characters gives 277,729 and 5,456 (2%). You can see where that is going. Almost all these coding challenges, for which basic solutions run too long, require such a careful analysis. They don't require fancy programming.