Loading…

mediumStringsFrequently asked

Sherlock and Anagrams

Q: How do you solve Sherlock and Anagrams using the Brute Force — Compare Every Substring Pair approach?

When to use it: State it to anchor correctness, then point out the O(n⁴) cost and replace the pairwise check with grouping. The literal reading: enumerate every substring, then test each unordered pair to see whether one is an anagram of the other. Count the pairs that pass. **The anagram test.** Two strings are anagrams iff they contain the same letters with the same multiplicities. You can check that by sorting both and comparing, or by comparing their 26-element frequency vectors. Either way, only equal-length substrings can possibly match, so you skip unequal lengths immediately. **Why it's correct.** It checks exactly the definition against every candidate pair — nothing is missed, nothing double-counted as long as you only consider pairs with the first index strictly before the second. **Why we don't ship this.** The substring count is `O(n²)`, so the number of pairs is `O(n⁴)`, and each comparison adds another factor. The redundancy is obvious: we compare the *same* substring against many others, re-deriving its signature every time. Computing each signature **once** and grouping by it removes the pairwise blow-up — that's the optimal approach. Time complexity: O(n⁴). Space complexity: O(n).

Arrays & Hashing · 34 of 83 · 10 min

Two strings are anagrams of each other if the letters of one can be rearranged to form the other.

Given a string s, count the number of pairs of substrings of s that are anagrams of each other. A substring is identified by its start and end positions, so two substrings with identical content but different positions are distinct.

Return the total number of unordered anagrammatic substring pairs.

In plain English

Every substring has a letter-frequency 'fingerprint'. Two substrings are anagrams precisely when their fingerprints match. So the problem reduces to: bucket all substrings by fingerprint, then within each bucket of k substrings count the C(k,2) ways to choose a pair.

Examples

Example 1

Input: s = "abba"
Output: 4
Note: Length-1: {a,a} → 1 pair, {b,b} → 1 pair. Length-2: {ab, ba} → 1. Length-3: {abb, bba} → 1. Total 4.

Example 2

Input: s = "abcd"
Output: 0
Note: All characters distinct, so no two substrings share a frequency signature — zero anagram pairs.

Example 3

Input: s = "kkkk"
Output: 10
Note: Length-1: C(4,2)=6. Length-2: C(3,2)=3. Length-3: C(2,2)=1. Length-4: C(1,2)=0. 6+3+1=10.

Constraints

1 ≤ s.length ≤ 100
s consists of lowercase English letters
Substrings are compared by content; position distinguishes otherwise-equal substrings
Pairs are unordered: (A, B) and (B, A) count once

Clarifying questions4First question: Are substrings distinguished by position?Explore questions

Q1.Are substrings distinguished by position?
Yes. In 'aa', the 'a' at index 0 and the 'a' at index 1 are two different substrings, so they form one anagram pair.
Q2.Do anagrams have to be the same length?
Yes — anagrams are reorderings, so they always share length. Keying on a length-sensitive signature (sorted chars or a count tuple) enforces this for free.
Q3.Are pairs ordered or unordered?
Unordered. That's why we use C(k,2) = k(k-1)/2, which counts each pair once, rather than k² or k(k-1).
Q4.Only lowercase letters?
Per the constraints, yes — a 26-slot count vector is enough. Mention you'd widen the alphabet otherwise.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count pairs of substrings that are anagrams of each other. Two substrings are anagrams exactly when they share the same letter-frequency signature, so group every substring by its signature and, for each group of size k, add C(k,2) = k(k-1)/2 pairs. Reduce a brute-force O(n⁴) pair check to an O(n²) grouping pass with a hash map keyed by signature.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise that anagram-equivalence becomes a hash-map grouping problem, and whether you count pairs with C(k,2) instead of off-by-one guesses like k or k².

Where candidates slip

Returning the group size k instead of C(k,2), or building the signature in a way that doesn't make anagrams collide (e.g. keying on the raw substring).

How to stand out

State the brute-force O(n⁴) baseline, then reduce it to grouping by a canonical signature, and derive C(k,2) explicitly as 'choose 2 of the k equal substrings'.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Compare Every Substring Pair	`O(n⁴)`	`O(n)`	State it to anchor correctness, then point out the O(n⁴) cost and replace the pairwise check with grouping.	Read
2	Group by Signature — Hash Map (Optimal)Optimal	`O(n³) (O(n²) substrings × O(n) signature)`	`O(n²)`	The answer they want. Phrase it as 'bucket substrings by their letter signature, then count C(k,2) per bucket'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAll substringsBucket size kYesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Compare Every Substring Pair

TimeO(n⁴)SpaceO(n)

State it to anchor correctness, then point out the O(n⁴) cost and replace the pairwise check with grouping.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

There are O(n²) substrings. The most direct count is to test every unordered pair of them for the anagram property.

2Hint 2Explore hint

Two substrings are anagrams iff sorting their characters yields the same string, or their 26-letter counts match. Only compare equal-length substrings.

3Hint 3Explore hint

O(n²) substrings → O(n⁴) pairs, and each comparison costs up to O(n). That's far too slow in general, but it pins down exactly what 'anagram pair' means.

A · Core idea

The literal reading: enumerate every substring, then test each unordered pair to see whether one is an anagram of the other. Count the pairs that pass.

The anagram test. Two strings are anagrams iff they contain the same letters with the same multiplicities. You can check that by sorting both and comparing, or by comparing their 26-element frequency vectors. Either way, only equal-length substrings can possibly match, so you skip unequal lengths immediately.

Why it's correct. It checks exactly the definition against every candidate pair — nothing is missed, nothing double-counted as long as you only consider pairs with the first index strictly before the second.

Why we don't ship this. The substring count is O(n²), so the number of pairs is O(n⁴), and each comparison adds another factor. The redundancy is obvious: we compare the same substring against many others, re-deriving its signature every time. Computing each signature once and grouping by it removes the pairwise blow-up — that's the optimal approach.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abba"

Array state

length 1

a, b, b, a → sorted unchanged

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

Reference implementation previewpublic int sherlockAndAnagrams(String s) { int n = s.length(); List<String> subs = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) {Explore the full code

solution.javaJava

Brute Force — Compare Every Substring Pair — reference

3 teaching notes

1
public int sherlockAndAnagrams(String s) {
2
    int n = s.length();
3
    List<String> subs = new ArrayList<>();
4
    for (int i = 0; i < n; i++) {
5
        for (int j = i + 1; j <= n; j++) {
6
            // Extract the substring s[i..j) to test.
7
            char[] c = s.substring(i, j).toCharArray();
8
            // Sorting canonicalises it — anagrams sort to the same string.
9
            Arrays.sort(c);
10
            subs.add(new String(c));
11
        }
12
    }
13
    int pairs = 0;
14
    for (int a = 0; a < subs.size(); a++) {
15
        for (int b = a + 1; b < subs.size(); b++) {
16
            // Equal sorted forms ⇔ anagrams. b starts at a+1 so each pair counts once.
17
            if (subs.get(a).equals(subs.get(b))) pairs++;
18
        }
19
    }
20
    return pairs;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n⁴) timeO(n) spaceOpen the invariant and proofExplore the proof

Every pairwise comparison re-discovers the same fact: substrings sharing a signature are anagrams. Compute the signature once per substring and let a hash map do the matching — pairs that share a key are pairs that match, with no explicit comparison.

ComplexityO(n⁴) time, O(n) space — There are n(n+1)/2 = O(n²) substrings, hence O(n⁴) unordered pairs. Each anagram check (sort or count) costs O(n), so the full cost is O(n⁴) to O(n⁵) depending on the check. Space is O(n) for one comparison buffer.

E · Edge cases and pitfalls3Comparing substrings of different lengths — wasted work; they can never be anagrams.Explore edge cases

Pitfalls

Comparing substrings of different lengths — wasted work; they can never be anagrams.
Counting ordered pairs (b from 0) — doubles the result.
Re-sorting the same substring repeatedly inside the pair loop — the source of the O(n⁴) cost.

03.2

Approach 2 of 2 · Optimal

Group by Signature — Hash Map (Optimal)

TimeO(n³) (O(n²) substrings × O(n) signature)SpaceO(n²)

The answer they want. Phrase it as 'bucket substrings by their letter signature, then count C(k,2) per bucket'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of comparing pairs, give each substring a canonical key so anagrams land in the same bucket. What key makes all anagrams equal?

2Hint 2Explore hint

Use a hash map from signature → count. The signature can be the sorted characters or, faster, a 26-length letter-count tuple. Increment the count for each substring.

3Hint 3Explore hint

After bucketing, a bucket holding k substrings contributes C(k,2) = k(k-1)/2 pairs. Sum that over all buckets.

A · Core idea

Stop comparing pairs and start grouping. Walk every substring once, reduce it to a canonical signature, and tally how many substrings share each signature in a hash map. Anagrams — and only anagrams — collide on the same key, so each bucket is a set of mutually-anagram substrings.

Choosing the signature. Two good keys:

Sorted characters: "ba" and "ab" both become "ab". Simple, and length is baked in (different lengths sort to different-length strings, so they never collide).
26-letter count tuple: record how many of each letter the substring has, e.g. (a:1, b:1). Building it is a single O(length) scan, and it's the more scalable key for large alphabets.

Either makes every pair of anagrams map to the identical key without an explicit comparison.

Why C(k,2), and why not k. Suppose a bucket holds k substrings that are all mutual anagrams. Every unordered pair drawn from those k is one valid anagram pair, and the number of such pairs is the binomial coefficient C(k,2) = k(k-1)/2. A bucket of 4 (like the four length-1 ks in "kkkk") gives 4·3/2 = 6 pairs — not 4, and not 12. Summing C(k,2) across all buckets is the final answer. Mis-remembering this as k or k(k-1) is the most common scoring error on this problem.

Why this beats brute force. Brute force re-derives each substring's signature for every comparison; here each signature is computed once and the hash map does the matching implicitly. We trade the O(n⁴) pair scan for an O(n²) grouping pass (times the O(n) signature build), and trade a little memory for the map.

Why the count must include position. We never deduplicate identical substrings — the two as in "aa" are two distinct substrings and legitimately form one pair. The map counts occurrences, so positional distinctness is preserved automatically.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abba"

Hash-map state

length-1 substrings

ValueIndex / state

a→ 2

b→ 2

Continue scanning

a:2, b:2 → 1 + 1 pairs

Final result4

C · Code with teaching comments

solution.javaJava

Group by Signature — Hash Map (Optimal) — optimal

4 teaching notes

1
public int sherlockAndAnagrams(String s) {
2
    // Signature → number of substrings sharing it. Anagrams collide here.
3
    Map<String, Integer> count = new HashMap<>();
4
    int n = s.length();
5
    for (int i = 0; i < n; i++) {
6
        for (int j = i + 1; j <= n; j++) {
7
            char[] c = s.substring(i, j).toCharArray();
8
            // Sorted characters are the canonical anagram key; length is implicit in
9
            // the key.
10
            Arrays.sort(c);
11
            String sig = new String(c);
12
            // Increment this signature's bucket — Java 21 merge keeps it to one line.
13
            count.merge(sig, 1, Integer::sum);
14
        }
15
    }
16
    int pairs = 0;
17
    for (int k : count.values()) {
18
        // C(k,2): unordered pairs within a bucket of k mutual anagrams.
19
        pairs += k * (k - 1) / 2;
20
    }
21
    return pairs;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n³) (O(n²) substrings × O(n) signature) timeO(n²) spaceOpen the invariant and proofExplore the proof

Replacing pairwise comparison with 'canonical key + bucket + combinatorial count' is a workhorse pattern. The hash map turns 'are these two equivalent?' (asked O(n⁴) times) into 'how many share this key?' (answered once per bucket), and C(k,2) converts a bucket size into its pair count in O(1).

ComplexityO(n³) (O(n²) substrings × O(n) signature) time, O(n²) space — There are O(n²) substrings; building each signature costs O(n) (scan its characters or sort), so populating the map is O(n³). Summing C(k,2) over buckets is O(n²). Space is O(n²) for the map of substring signatures.

E · Edge cases and pitfalls6s = "a" — Only one substring; its bucket has count 1 → C(1,2)=0 → returns 0.Explore edge cases

Edge cases handled

s = "a"Only one substring; its bucket has count 1 → C(1,2)=0 → returns 0.
s = "abcd"All signatures distinct, every bucket count is 1 → sum of C(1,2) = 0.
s = "kkkk"Buckets of size 4,3,2,1 → 6+3+1+0 = 10. Shows C(k,2) growing quadratically with repeats.

Pitfalls

Adding k instead of C(k,2) — undercounts every bucket of size ≥ 3.
Keying on the raw substring instead of a canonical signature — anagrams never collide.
Using float division (k*(k-1)/2 in Python) — use // to stay an integer.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int sherlockAndAnagrams(String s) { Map<String, Integer> count = new HashMap<>(); int n = s.length(); for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning k instead of C(k,2)

A bucket of k mutual anagrams yields k(k-1)/2 unordered pairs, not k. On 'kkkk' the length-1 bucket of 4 gives 6 pairs, but adding k would give 4.

Explore the code comparison

Don't write this

return sum(count.values())  # adds bucket sizes, not pairs

Write this instead

return sum(k * (k - 1) // 2 for k in count.values())

Keying on the raw substring

If the map key is the substring itself, 'ab' and 'ba' get separate buckets and are never recognised as anagrams. The key must be a canonical form.

Explore the code comparison

Don't write this

String sig = s.substring(i, j);   // 'ab' and 'ba' differ
count.merge(sig, 1, Integer::sum);

Write this instead

char[] c = s.substring(i, j).toCharArray();
Arrays.sort(c);
String sig = new String(c);        // 'ab' and 'ba' both → 'ab'
count.merge(sig, 1, Integer::sum);

Float division in the pair count

In Python, k*(k-1)/2 produces a float (e.g. 6.0), which is wrong for a count and can break equality checks. Use integer division //.

Explore the code comparison

Don't write this

pairs += k * (k - 1) / 2   # 6.0, a float

Write this instead

pairs += k * (k - 1) // 2  # 6, an int

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Group by canonical signature, then count pairs with C(k,2)

Code pattern to memorize

count = {}
for each substring sub:
    sig = canonical(sub)   # sorted chars OR letter-count tuple
    count[sig] += 1
return sum(k*(k-1)//2 for k in count.values())

Rules to remember

1Anagram ⇔ identical letter-frequency signature. Pick a canonical form so all anagrams collapse to the same key.
2From a group of k mutually-anagram substrings, the number of unordered pairs is C(k,2) = k(k-1)/2 — not k.
3Only compare substrings of the same length; using sorted-chars or a count tuple as the key enforces that automatically (different lengths → different keys).
4Count substrings by content and position: the two 'a's in "aa" are distinct substrings, so they form one valid pair.
5Use a frequency tuple (or sorted string) as the key — never the raw substring, or anagrams won't collide.

Use this pattern when

Counting or grouping items that are equal up to reordering (anagrams)
'How many pairs share property X' where X has a canonical signature
Bucketing strings/arrays by a normalized key, then combining within buckets
Any problem reducible to 'group, then count pairs per group'

Choose another pattern when

Need the actual pairs, not just the count → store members per bucket (more memory)
Substrings must be contiguous AND you need longest/shortest → different (often two-pointer) technique
Comparing whole strings only, not all substrings → a single grouping pass, no n² enumeration
Order matters (not anagrams) → key on the raw string, not a signature

Interview takeaway

The reusable move is 'reduce equivalence to a canonical key, bucket by it, then count pairs with C(k,2)'. The same shape powers Group Anagrams, counting equal rows/columns, and any 'how many pairs are equivalent' question.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 'group by signature, count with C(k,2)'. Reduce an equivalence (anagram) to a canonical key, bucket in a hash map, then convert bucket sizes to pair counts combinatorially. Same shape as Group Anagrams and counting equal rows/columns in a matrix.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Group Anagrams
Same signature-bucketing, but return the groups instead of a pair count.
Valid Anagram
The atomic check underneath: compare two letter-count signatures.
Find All Anagrams in a String
Coming soon
Fixed-length anagram matching via a sliding-window frequency count.
Permutation in String
Window frequency match — does any window equal the pattern's signature?

Same pattern

←

Mars Exploration

Continue · Next problem

Strong Password

mediumStringsFrequently asked

Sherlock and Anagrams

Arrays & Hashing · 34 of 83 · 10 min

Two strings are anagrams of each other if the letters of one can be rearranged to form the other.

Return the total number of unordered anagrammatic substring pairs.

In plain English

Examples

Example 1

Input: s = "abba"
Output: 4
Note: Length-1: {a,a} → 1 pair, {b,b} → 1 pair. Length-2: {ab, ba} → 1. Length-3: {abb, bba} → 1. Total 4.

Example 2

Input: s = "abcd"
Output: 0
Note: All characters distinct, so no two substrings share a frequency signature — zero anagram pairs.

Example 3

Input: s = "kkkk"
Output: 10
Note: Length-1: C(4,2)=6. Length-2: C(3,2)=3. Length-3: C(2,2)=1. Length-4: C(1,2)=0. 6+3+1=10.

Constraints

1 ≤ s.length ≤ 100
s consists of lowercase English letters
Substrings are compared by content; position distinguishes otherwise-equal substrings
Pairs are unordered: (A, B) and (B, A) count once

Clarifying questions4First question: Are substrings distinguished by position?Explore questions

Q1.Are substrings distinguished by position?
Yes. In 'aa', the 'a' at index 0 and the 'a' at index 1 are two different substrings, so they form one anagram pair.
Q2.Do anagrams have to be the same length?
Yes — anagrams are reorderings, so they always share length. Keying on a length-sensitive signature (sorted chars or a count tuple) enforces this for free.
Q3.Are pairs ordered or unordered?
Unordered. That's why we use C(k,2) = k(k-1)/2, which counts each pair once, rather than k² or k(k-1).
Q4.Only lowercase letters?
Per the constraints, yes — a 26-slot count vector is enough. Mention you'd widen the alphabet otherwise.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise that anagram-equivalence becomes a hash-map grouping problem, and whether you count pairs with C(k,2) instead of off-by-one guesses like k or k².

Where candidates slip

Returning the group size k instead of C(k,2), or building the signature in a way that doesn't make anagrams collide (e.g. keying on the raw substring).

How to stand out

State the brute-force O(n⁴) baseline, then reduce it to grouping by a canonical signature, and derive C(k,2) explicitly as 'choose 2 of the k equal substrings'.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Compare Every Substring Pair	`O(n⁴)`	`O(n)`	State it to anchor correctness, then point out the O(n⁴) cost and replace the pairwise check with grouping.	Read
2	Group by Signature — Hash Map (Optimal)Optimal	`O(n³) (O(n²) substrings × O(n) signature)`	`O(n²)`	The answer they want. Phrase it as 'bucket substrings by their letter signature, then count C(k,2) per bucket'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Compare Every Substring Pair

TimeO(n⁴)SpaceO(n)

State it to anchor correctness, then point out the O(n⁴) cost and replace the pairwise check with grouping.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

There are O(n²) substrings. The most direct count is to test every unordered pair of them for the anagram property.

2Hint 2Explore hint

Two substrings are anagrams iff sorting their characters yields the same string, or their 26-letter counts match. Only compare equal-length substrings.

3Hint 3Explore hint

O(n²) substrings → O(n⁴) pairs, and each comparison costs up to O(n). That's far too slow in general, but it pins down exactly what 'anagram pair' means.

A · Core idea

The literal reading: enumerate every substring, then test each unordered pair to see whether one is an anagram of the other. Count the pairs that pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abba"

Array state

length 1

a, b, b, a → sorted unchanged

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Brute Force — Compare Every Substring Pair — reference

3 teaching notes

1
public int sherlockAndAnagrams(String s) {
2
    int n = s.length();
3
    List<String> subs = new ArrayList<>();
4
    for (int i = 0; i < n; i++) {
5
        for (int j = i + 1; j <= n; j++) {
6
            // Extract the substring s[i..j) to test.
7
            char[] c = s.substring(i, j).toCharArray();
8
            // Sorting canonicalises it — anagrams sort to the same string.
9
            Arrays.sort(c);
10
            subs.add(new String(c));
11
        }
12
    }
13
    int pairs = 0;
14
    for (int a = 0; a < subs.size(); a++) {
15
        for (int b = a + 1; b < subs.size(); b++) {
16
            // Equal sorted forms ⇔ anagrams. b starts at a+1 so each pair counts once.
17
            if (subs.get(a).equals(subs.get(b))) pairs++;
18
        }
19
    }
20
    return pairs;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n⁴) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Comparing substrings of different lengths — wasted work; they can never be anagrams.Explore edge cases

Pitfalls

Comparing substrings of different lengths — wasted work; they can never be anagrams.
Counting ordered pairs (b from 0) — doubles the result.
Re-sorting the same substring repeatedly inside the pair loop — the source of the O(n⁴) cost.

03.2

Approach 2 of 2 · Optimal

Group by Signature — Hash Map (Optimal)

TimeO(n³) (O(n²) substrings × O(n) signature)SpaceO(n²)

The answer they want. Phrase it as 'bucket substrings by their letter signature, then count C(k,2) per bucket'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of comparing pairs, give each substring a canonical key so anagrams land in the same bucket. What key makes all anagrams equal?

2Hint 2Explore hint

Use a hash map from signature → count. The signature can be the sorted characters or, faster, a 26-length letter-count tuple. Increment the count for each substring.

3Hint 3Explore hint

After bucketing, a bucket holding k substrings contributes C(k,2) = k(k-1)/2 pairs. Sum that over all buckets.

A · Core idea

Choosing the signature. Two good keys:

Sorted characters: "ba" and "ab" both become "ab". Simple, and length is baked in (different lengths sort to different-length strings, so they never collide).
26-letter count tuple: record how many of each letter the substring has, e.g. (a:1, b:1). Building it is a single O(length) scan, and it's the more scalable key for large alphabets.

Either makes every pair of anagrams map to the identical key without an explicit comparison.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abba"

Hash-map state

length-1 substrings

ValueIndex / state

a→ 2

b→ 2

Continue scanning

a:2, b:2 → 1 + 1 pairs

Final result4

C · Code with teaching comments

solution.javaJava

Group by Signature — Hash Map (Optimal) — optimal

4 teaching notes

1
public int sherlockAndAnagrams(String s) {
2
    // Signature → number of substrings sharing it. Anagrams collide here.
3
    Map<String, Integer> count = new HashMap<>();
4
    int n = s.length();
5
    for (int i = 0; i < n; i++) {
6
        for (int j = i + 1; j <= n; j++) {
7
            char[] c = s.substring(i, j).toCharArray();
8
            // Sorted characters are the canonical anagram key; length is implicit in
9
            // the key.
10
            Arrays.sort(c);
11
            String sig = new String(c);
12
            // Increment this signature's bucket — Java 21 merge keeps it to one line.
13
            count.merge(sig, 1, Integer::sum);
14
        }
15
    }
16
    int pairs = 0;
17
    for (int k : count.values()) {
18
        // C(k,2): unordered pairs within a bucket of k mutual anagrams.
19
        pairs += k * (k - 1) / 2;
20
    }
21
    return pairs;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n³) (O(n²) substrings × O(n) signature) timeO(n²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = "a" — Only one substring; its bucket has count 1 → C(1,2)=0 → returns 0.Explore edge cases

Edge cases handled

s = "a"Only one substring; its bucket has count 1 → C(1,2)=0 → returns 0.
s = "abcd"All signatures distinct, every bucket count is 1 → sum of C(1,2) = 0.
s = "kkkk"Buckets of size 4,3,2,1 → 6+3+1+0 = 10. Shows C(k,2) growing quadratically with repeats.

Pitfalls

Adding k instead of C(k,2) — undercounts every bucket of size ≥ 3.
Keying on the raw substring instead of a canonical signature — anagrams never collide.
Using float division (k*(k-1)/2 in Python) — use // to stay an integer.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning k instead of C(k,2)

A bucket of k mutual anagrams yields k(k-1)/2 unordered pairs, not k. On 'kkkk' the length-1 bucket of 4 gives 6 pairs, but adding k would give 4.

Explore the code comparison

Don't write this

return sum(count.values())  # adds bucket sizes, not pairs

Write this instead

return sum(k * (k - 1) // 2 for k in count.values())

Keying on the raw substring

If the map key is the substring itself, 'ab' and 'ba' get separate buckets and are never recognised as anagrams. The key must be a canonical form.

Explore the code comparison

Don't write this

String sig = s.substring(i, j);   // 'ab' and 'ba' differ
count.merge(sig, 1, Integer::sum);

Write this instead

char[] c = s.substring(i, j).toCharArray();
Arrays.sort(c);
String sig = new String(c);        // 'ab' and 'ba' both → 'ab'
count.merge(sig, 1, Integer::sum);

Float division in the pair count

In Python, k*(k-1)/2 produces a float (e.g. 6.0), which is wrong for a count and can break equality checks. Use integer division //.

Explore the code comparison

Don't write this

pairs += k * (k - 1) / 2   # 6.0, a float

Write this instead

pairs += k * (k - 1) // 2  # 6, an int

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Group by canonical signature, then count pairs with C(k,2)

Code pattern to memorize

count = {}
for each substring sub:
    sig = canonical(sub)   # sorted chars OR letter-count tuple
    count[sig] += 1
return sum(k*(k-1)//2 for k in count.values())

Rules to remember

1Anagram ⇔ identical letter-frequency signature. Pick a canonical form so all anagrams collapse to the same key.
2From a group of k mutually-anagram substrings, the number of unordered pairs is C(k,2) = k(k-1)/2 — not k.
3Only compare substrings of the same length; using sorted-chars or a count tuple as the key enforces that automatically (different lengths → different keys).
4Count substrings by content and position: the two 'a's in "aa" are distinct substrings, so they form one valid pair.
5Use a frequency tuple (or sorted string) as the key — never the raw substring, or anagrams won't collide.

Use this pattern when

Counting or grouping items that are equal up to reordering (anagrams)
'How many pairs share property X' where X has a canonical signature
Bucketing strings/arrays by a normalized key, then combining within buckets
Any problem reducible to 'group, then count pairs per group'

Choose another pattern when

Need the actual pairs, not just the count → store members per bucket (more memory)
Substrings must be contiguous AND you need longest/shortest → different (often two-pointer) technique
Comparing whole strings only, not all substrings → a single grouping pass, no n² enumeration
Order matters (not anagrams) → key on the raw string, not a signature

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Group Anagrams
Same signature-bucketing, but return the groups instead of a pair count.
Valid Anagram
The atomic check underneath: compare two letter-count signatures.
Find All Anagrams in a String
Coming soon
Fixed-length anagram matching via a sliding-window frequency count.
Permutation in String
Window frequency match — does any window equal the pattern's signature?

Same pattern

←

Mars Exploration

Continue · Next problem

Strong Password