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