from collections import defaultdict

def sherlockAndAnagrams(s):
    def get_frequency_hash(freq):
        return tuple(freq)

    n = len(s)
    anagram_count = 0
    freq_map = defaultdict(int)

    # Calculate cumulative frequency for each position
    cum_freq = [[0] * 26 for _ in range(n + 1)]
    for i in range(1, n + 1):
        cum_freq[i] = cum_freq[i-1][:]
        cum_freq[i][ord(s[i-1]) - ord('a')] += 1

    # Count frequency differences
    for length in range(1, n):
        freq_map.clear()
        for i in range(n - length + 1):
            j = i + length
            freq_diff = [cum_freq[j][k] - cum_freq[i][k] for k in range(26)]
            freq_hash = get_frequency_hash(freq_diff)
            freq_map[freq_hash] += 1

        # Calculate anagram pairs
        for count in freq_map.values():
            anagram_count += count * (count - 1) // 2

    return anagram_count

public static int sherlockAndAnagrams(String s) {
        int count = 0;
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String substring = s.substring(i, j);
                char[] chars = substring.toCharArray();
                Arrays.sort(chars);
                String sortedSubstring = new String(chars);

                map.put(sortedSubstring, map.getOrDefault(sortedSubstring, 0) + 1);
            }
        }

        for (int value : map.values()) {
            count += value * (value - 1) / 2; // combination formula is n * (n - 1) / 2
        }

        return count;
    }

    public static int sherlockAndAnagrams(String s) {
        Map<String, Integer> occurrences = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String val = sortString(s.substring(i, j + 1));
                occurrences.put(val, occurrences.getOrDefault(val, 0) + 1);
            }
        }
        int anagramPairCount = 0;
        occurrences = removeSingleOccurrences(occurrences);
        for (Map.Entry<String, Integer> e : occurrences.entrySet()) {
            // Once occurrence ‘o’ of each frequency array is stored, total anagrams will be the sum of
            // o*(o-1)/2 for all different frequency arrays because if a particular substring has ‘o’ anagrams in
            // string total o*(o-1)/2 anagram pairs can be formed. Below is the implementation of above idea.

            // The division by two is needed to disregard different combinations between two elements:
            // [0, 1] and [1, 0]
            anagramPairCount += (e.getValue() * (e.getValue() - 1)) / 2;
        }
        return anagramPairCount;
    }

    private static Map<String, Integer> removeSingleOccurrences(Map<String, Integer> occurrences) {
        return occurrences
            .entrySet()
            .stream()
            .filter(e -> e.getValue() > 1)
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
    }

    private static String sortString(String str) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        return String.valueOf(charArray);
    }

    public static int sherlockAndAnagrams(string s)
    {
        int pairsCount = 0;
        Dictionary<string, List<string>> subs = 
            new Dictionary<string, List<string>>();
        
        for (int l = 1; l <= s.Length; l++) {
            for (int i = 0; i <= s.Length - l; i++) {
                string subStr = s.Substring(i, l);
                string hc = GetHashCode(subStr);
                if (!subs.ContainsKey(hc))
                    subs.Add(hc, new List<string>());
                subs[hc].Add(subStr);                
            }
        }
        
        foreach (var kv in subs) {
            if (kv.Value.Count() > 1)
                pairsCount += (kv.Value.Count() * (kv.Value.Count()-1))/2;
        }
        
        return pairsCount;
    }
    
    private static string GetHashCode(string subStr) {
        int[] chars = new int[26];
        foreach (char ch in subStr) {
            chars[(int)(ch - 'a')]++;
        }
        var strCodes = chars.Select(c => c.ToString());
        return string.Join("", strCodes);
    }

int sherlockAndAnagrams(string s) {
    int n = s.size();
    int anagram_count;
    
    for (int i = 1; i < n; i++){// i for size of substrings
    
    unordered_map<string, int> store;
    string substring;
    
        for (int j = 0; j < n-i+1; j++){// j for the starting position of the substring
        
            substring = s.substr(j,i); // substring starting at position j of length i
            
            sort(substring.begin(), substring.end()); // sort the substring
            
            store[substring]++; //count the number of times substring appears, up to rearrangement
        }
        for (auto t : store){
            if (t.second > 1){
                anagram_count += (t.second)*(t.second-1)/2; // number of pairs is n choose 2 if n appears more than twice
            }
        }
    }
    return anagram_count;
}