Hackerrank.com - Sherlock and Anagrams

Question

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 = '') => {
    let count = 0
    let pairs = []
    for (let wordSize = 1; wordSize < s.length; wordSize++) {
        for (let wordPosition = 0; wordPosition < 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 < pairs.length; i++) {
        const word = pairs[i]
        pairs.forEach((value, index) => {
            if (word.wordPosition !== value.wordPosition && index !== i && 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', () => {
  const s = 'mom'
  const expected = 2
  const result = anagrams(s)
  expect(result).toBe(expected)
})

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

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

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

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

test('F - Given a string return pairs of anagrams', () => {
  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', () => {
  const s = 'ifailuhkqqhucpoltgtyovarjsnrbfpvmupwjjjfiwwhrlkpekxxnebfrwibylcvkfealgonjkzwlyfhhkefuvgndgdnbelgruel'
  const expected = 399
  const result = anagrams(s)
  expect(result).toBe(expected)
})

test('H - Given a string return pairs of anagrams', () => {
  const s = 'gffryqktmwocejbxfidpjfgrrkpowoxwggxaknmltjcpazgtnakcfcogzatyskqjyorcftwxjrtgayvllutrjxpbzggjxbmxpnde'
  const expected = 471
  const result = anagrams(s)
  expect(result).toBe(expected)
})

Answer 1

Check each unique sub string once

I agree with the existing answer, however there is a faster way to solve the problem, there is also an early exit possible that many of the challenges will test for.

The early exit can be found by finding out if there are any two characters that are the same. If not then there are no anagrams that are longer than 1 character an thus you can exit with a result of 0

Using a Map you can count unique anagrams as you go. Each time you find an existing anagram you add to the total count the number of that anagram already found, then add one to that anagram.

The solution complexity is set by the number of characters in the input string (ignoring the early exit) and not related to the string length and number of anagrams as your function does

For a 28 character string the solution can be found in 405 iterations compared to your ~550,000 or ~4,059 for the existing answer.

function anagramCounts(str) {
    const found = new Map();
    var i,end, subLen = 1, count = 0, counts;
    while (subLen < str.length) {
        end = (i = 0) + subLen++;
        while (end <= str.length) {
            const sorted = [... str.substring(i++, end++)].sort().join("");   
            if (!found.has(sorted)) { found.set(sorted, [1]) }
            else { count += (counts = found.get(sorted))[0]++ }
        }
    }
    return count;
}

Some additional optimizations

The sort is also a where complexity grows. Because you need to pass over whole string once to find single characters you could also optimize the sort as you will know the relative order of each character to its neighbors after the first pass.

After the first pass you will know which characters will not be part of longer anagrams (those that appear only once).

You can replace all single instance characters with a symbol after the first pass. Then replace any sequence of 2 or more symbols with a single symbol. This reduces the total string length that needs to be tested in further passes, and also provides a way to avoid sorting a sub string if it contains the symbol.

Answer 2

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.

1. 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.
2. 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.
3. 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 < s.length; len++) {
        var parts = [];
        for (var pos = 0; pos <= s.length - len; pos++) {
            var part = s.substr(pos, len);
            parts.push(part.split('').sort().join(''));
        }
        for (var index1 = 0; index1 < parts.length; index1++) {
            var part1 = parts[index1];
            for (var index2 = index1 + 1; index2 < 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.