5
\$\begingroup\$

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)
})
\$\endgroup\$
  • \$\begingroup\$ @200_success sorry ! \$\endgroup\$ – Thiago Caramelo May 6 at 17:39
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, this is certainly fancier than my answer. I like the idea of using map storage for counting. You get my upvote for that. However, in the end, I cannot measure a real improvement in speed. That surprised me. I used Firefox, a 60 chrs string, and performance.now();. Your solution should be faster because it clearly uses less iterations, but it doesn't seem to be. Perhaps because my iterations are so simple? Oh, wait, in Chrome your solution is about twice as fast, but that's basically because Chrome is quite a bit slower for my solution. Clearly Firefox is more optimized. \$\endgroup\$ – KIKO Software May 7 at 11:18
  • \$\begingroup\$ @KIKOSoftware I think you will find that it is how I split the string [...str] is much slower than str.split() due to behavioral differences. For ASCII str.split can be used and will give a big improvement in performance (maybe 3 times as fast), For unicode then the safer method is via the string iterator [...str] \$\endgroup\$ – Blindman67 May 7 at 14:19
  • \$\begingroup\$ Tested that, and I found no significant differences. I didn't try different encodings (standard HTML5 page). \$\endgroup\$ – KIKO Software May 7 at 15:05
  • \$\begingroup\$ @Blindman67. I'm afraid your second code did not pass the tests. The first is ok. \$\endgroup\$ – Thiago Caramelo May 7 at 16:44
  • \$\begingroup\$ @ThiagoCaramelo thanks for the feedback. I am unsure why the second failed, I will remove it from the answer. \$\endgroup\$ – Blindman67 May 7 at 19:41
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

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