Sherlock and Anagrams in Javascript

Question

I am trying to solve a Hackerrank problem Sherlock and Anagrams. I think my code is valid but somehow times out for some of the test cases. Any tips on how to improve its performance? Critique unrelated to performance is welcome as well!

Here is my main method which gets a string as an input and returns an integer that represents the number of pairs of substrings of the string that are anagrams of each other:

function sherlockAndAnagrams(s) {

    let substrings = [];
    let pairs = [];

    // get all substrings
    for (let i = 0; i < s.length+1; i++) {
        for (let j = i+1; j < s.length+1; j++) {
            substrings.push(s.substring(i, j));
        }
    }
    
    // sort substrings so they can be compared using ===
    substrings = substrings.map(sub => [...sub].sort().join(""));

    // count them by comparing each with each skipping the ones with different length
    return substrings.reduce((counter, sub, index, arr) => {
        return counter += arr.reduce((acc, item, jndex) => {
            if (sub.length === item.length && sub === item && index !== jndex) {
                let uid = [index, jndex].sort().join("");
                if (!pairs.includes(uid)) {
                    acc++;
                    pairs.push(uid);
                }
            }
            return acc;
        }, 0);
    }, 0);
}

Here is a shortened version of the problem description as additional context:

Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string. Given a string, find the number of pairs of substrings of the string that are anagrams of each other.

sherlockAndAnagrams has the following parameter: s: a string

It must return an integer that represents the number of anagrammatic pairs of substrings in s. For each query, return the number of unordered anagrammatic pairs.

Answer 1

comparing each with each means the quadratic time complexity, and skipping the ones with different length does not improve the bottomline.

Sort the set of (sorted) substrings, and the anagrams will form contiguous runs. The run of length \$k\$ produces \$\dfrac{k(k-1)}{2}\$ pairs.

---

Example:

An original array:

ab
cde
xy
dec
ba
ced

After each string has been sorted, it becomes

ab
cde
xy
cde
ab
cde

Now, after the entire array is sorted lexicographically, it becomes

ab
ab
cde
cde
cde
xy

The ab, ab and cde, cde, cde form the contiguous (that is, uninterrupted) runs, of length 2 and 3 respectively.

Answer 2

I am a javascript beginner, let me know the ways how I can improve my answer; every suggestion is welcome.

The problem can be divided in two parts:

1. Part 1 : how to calculate number of pairs from a set of elements
2. Part 2 : given one string , extract all the substrings inside the main string and find calculate the number of pairs of strings that are anagrams one of the other.

Part1

The number of the pairs from a set of n elements can be calculated with the formula npairs = n! / (2 * (n - 2)!) = (n * (n - 1)) / 2, below one function to calculate the number of pairs:

function countPairs(n) {
    return (n * (n - 1)) / 2;
}

The countPairs function will return the numbers of pairs from a set of n elements and it is used in the part2.

Part2

To store anagrams you can use a Map structure storing anagrams and their occurrences , so if you have for example two strings ab and ba the map['ab'] will be 2. Once you stored all the substrings inside your map you will iterate over it to return the sum of the pairs found. So for example if you have in your map map['ab'] = 3 (three substring anagrams found) the number of pairs will be determined calling countPairs(3). If you have for example map['cc'] = 1 then it is not possible to create pairs and it will excluded from the calculus of the sum of the pairs. Below the sherlockAndAnagrams function:

function sherlockAndAnagrams(s) {
    const map = new Map();
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        for (let j = i; j < n; ++j) {
            const sub = s.substring(i, j + 1);
            const key = sub.split('').sort().join('');
            if (map.has(key)) {
               map.set(key, map.get(key) + 1); 
            } else {
               map.set(key, 1);
            }
        }
    }  //done , substrings stored in the map

    //Check all map values and calculate number of pairs 
    //for every key with an associate value > 1
    let result = 0;
    for (const [key, value] of map) {
        if (value > 1) {
         result += countPairs(value);    
        }
    }
    return result;
}

I tried it on the Hackerrank site, passing all tests.