We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Sherlock and Anagrams
  5. Discussions

Sherlock and Anagrams

Sort by

recency

|

1698 Discussions

|

  • ajvnho
     + 0 comments

    A short CPP version:

    int sherlockAndAnagrams(std::string s) {
    std::map<std::map<char,int>, int> unique_strings;
    int result = 0;
    for (size_t i = 0; i<s.size(); ++i){
        std::map<char,int> submap;
        for (size_t j = i; j<s.size(); ++j) {
            submap[s[j]]++;
            unique_strings[submap]++;
        }
    }
    for (auto& [substr, count]: unique_strings) {
        result += (count - 1)* count / 2;
    }
    return result;
}

  • saberelharti
     + 0 comments

    Here's the approch that I implement to solve this problem with Kotlin: 

    fun sherlockAndAnagrams(s: String): Int {
    var windowedSize = s.length - 1 // define possible windowed steps for that string
    var listOfWindows : List<List<Char>> = listOf()
    var anagramsCounter = 0
    
    // itterate based on possible windowed steps
    while(windowedSize > 0){
        // get all windowed sets
        listOfWindows = s.toList().windowed(size = windowedSize, step = 1) { it ->
            it.sortedBy { it }
        }
        // count all anagrams
        listOfWindows.forEachIndexed{ index, window ->
            for(j in (index + 1) .. listOfWindows.lastIndex) {
                if(window == listOfWindows[j])  
                    anagramsCounter++
            }
        }
        windowedSize-- // reduce the windowed size
    }
    return anagramsCounter
}

  • paulelrich7
     + 0 comments

    I wanted to use the NCR formula to count permutations, which uses factorials.

    100! is a very big number. (9e157)

    Luckily c# has the arbitrary System.Numerics.BigInteger

  • cherkashin_i_a
     + 0 comments

    python (NOTE replace '@' with ':' - HackerRank didn't allow to upload this comment when having ':' in the text).

    import itertools
def sherlockAndAnagrams(s):
    return sum([
    len([
        pair
        for pair in itertools.combinations([s[i@i+l] for i in range(len(s) - l + 1)], 2)
        if sorted(pair[0]) == sorted(pair[1])
    ])
    for l in range(1, len(s))
    ])

  • romedsoft
     + 0 comments
    static string sortString(string s) {
        const int MAX_CHAR = 26;
        int[] charCount = new int[MAX_CHAR];
        StringBuilder sb = new StringBuilder();
        
        foreach (char ch in s) {
            charCount[ch - 'a']++;
        }
        
        for (int i = 0; i < MAX_CHAR; i++) {
            for (int j = 0; j < charCount[i]; j++) {
                sb.Append('a' + i);
            }
        }
        
        return sb.ToString();
    }
    
    static int calculateTotalCombinations(int n){    
        return (n * (n -1)) / 2;
    }
    
    static Dictionary<string, int> findSubstrings(string s) 
    {  
        Dictionary<string, int> dic = new Dictionary<string, int>();
    
        for(int i = 1; i <= s.Length; i++) 
        { 
            for(int j = 0; j <= s.Length - i; j++) 
            {   
                var substring = sortString(s.Substring(j, i));
                
                // Using Substring() function 
                if(dic.ContainsKey(substring)){
                  dic[substring] = dic[substring] + 1; 
                  continue; 
                }
                
                dic.Add(substring, 1);
            } 
        } 
        
        return dic;
    } 

    public static int sherlockAndAnagrams(string s)
    {
        var dic = findSubstrings(s);
        int totalAnagrams = 0;
        
        foreach(var item in dic){
            totalAnagrams+= calculateTotalCombinations(item.Value); 
        }
        
        return totalAnagrams;
    }