Simple anagram pairs
Input
count_anagrammatic_pairs("abba")
Output
4
Substrings that form anagrammatic pairs: ('a','a'), ('b','b'), ('ab','ba'), ('abb','bba') -> 4 pairs.
Full lesson preview
Count anagrammatic substring pairs
Count unordered pairs of substrings of a string that are anagrams of each other using frequency-signature grouping.
Python practice24 minStrings – Sliding Window & FrequencyAdvancedLast updated March 25, 2026
Problem statement
Given a string s containing only lowercase English letters, find the number of unordered pairs of substrings of s that are anagrams of each other. Two substrings are an anagrammatic pair if they consist of the same multiset of characters (order doesn't matter). For example, in 'abba' the substrings 'a' (positions 0 and 3) form a pair, 'b' (positions 1 and 2) form a pair, 'ab' (positions 0-1) and 'ba' (positions 2-3) form a pair, and 'abb' and 'bba' form a pair: total 4 pairs.
Design an algorithm that groups substrings by character-frequency signature and counts pairs efficiently.
Task
Given a lowercase string, compute how many unordered pairs of substrings are anagrams of one another using frequency counting and combinatorics.
Examples
Input format
A single function call: count_anagrammatic_pairs(s) where s is a lowercase string.
Output format
Return an integer representing the number of unordered anagrammatic substring pairs.
Constraints
1 <= len(s) <= 2000 (solutions up to O(n^2) are acceptable). s contains only 'a' to 'z'.
Samples
Sample 1
Input
count_anagrammatic_pairs("kkkk")
Output
10
All substrings are anagrams among same lengths: total 10 unordered pairs.