0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ @MartinR Stop overcomplicating this. The question was not answered as in solved. I implemented an idea that did not solve the problem. I will not ask a new question about the same thing with similar code. \$\endgroup\$
    – leonheess
    May 4, 2020 at 11:53
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. I have locked the question for a day for now. \$\endgroup\$
    – Vogel612
    May 4, 2020 at 11:58

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ i have been watching this video (youtu.be/3fpSbdzR6Pc?t=768) a few times and googling this formula - I really do not understand how you/he came up to it (I not a computer science student) - can you help me figure this out? what should I research? can you simplify how you got to the formula for me please? \$\endgroup\$
    – Kar19
    Sep 30, 2020 at 19:36
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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