Loading…

easyStrings0Sometimes asked

Anagram

Q: How do you solve Anagram using the Sort Each Half and Compare Letter Counts (Baseline) approach?

When to use it: Mention to show you understand 'anagram = same multiset', then note sorting is overkill versus counting. The definition of anagram is 'same characters with the same multiplicities'. A natural first instinct is to sort each half so equal multisets line up, then measure how far apart they are. **Why sorting feels right but is the long way around.** Sorting groups identical letters together, so two anagrams become byte-identical after sorting. To *count edits*, though, you don't actually care about order at all — you care about how many of each letter each half holds. Sorting throws away nothing useful but adds a log-factor and forces you to re-derive counts by scanning runs. **Why we move on.** The whole computation is a histogram comparison. A histogram is built in one O(n) pass with a 26-slot array; sorting is strictly more work for the same information. Open with this to prove you know the anagram definition, then replace it with frequency counting. Time complexity: O(n log n). Space complexity: O(n).

Q: How do you solve Anagram using the Single Frequency-Difference Pass (Optimal) approach?

When to use it: The answer they want — frame it as 'one histogram of (firstHalf − secondHalf), then sum the positives'. Maintain a single `int[26]` balance array. Walk the first half adding `+1` to each letter's slot, then walk the second half subtracting `1`. After both passes, slot `c` holds `freq_a(c) − freq_b(c)`. The minimum number of changes is the sum of the *positive* slots. **Why positive slots are exactly the edit count.** A positive value at letter `c` means the first half has that many more `c`s than the second half. To make the second half an anagram, each of those missing `c`s must be created by *replacing* some other character in the second half. Crucially, the surplus letters in `a` and the deficit letters in `b` come in matched pairs: every `+1` somewhere is balanced by a `−1` elsewhere, because both halves have the same length. So one replacement simultaneously removes a surplus and fills a deficit. Counting just the positives (or equivalently `sum(|balance|)/2`) avoids double-counting that single fix. **Why O(1) space.** The alphabet is fixed at 26 letters, so the balance array never grows with `n`. That is the line to say aloud: 'O(n) time, O(1) space because the alphabet is constant.' **Why the odd guard comes first.** If `n` is odd the halves differ in size and no number of replacements can equalise the multisets — return −1 before touching the array. Time complexity: O(n). Space complexity: O(1).

Arrays & Hashing · 62 of 83 · 7 min

Given a string s, split it into two halves: the first half a and the second half b. Determine the minimum number of character changes needed to make b an anagram of a (changing a character means replacing it with any other character).

If the length of s is odd, the two halves cannot have equal length, so it is impossible — return -1.

In plain English

Anagram means same letters, same counts, any order. Splitting `s` in half gives two windows of equal size (when the length is even). We may rewrite letters in the second half; the cheapest way to make it an anagram of the first is to count, per letter, how many extra copies the first half has that the second lacks — each such surplus is one forced replacement.

Examples

Example 1

Input: s = "aaabbb"
Output: 3
Note: a = "aaa", b = "bbb". The first half has 3 surplus 'a's that the second half lacks, so all 3 'b's must become 'a's. 3 changes.

Example 2

Input: s = "xaxbbbxx"
Output: 1
Note: a = "xaxb" (x:2, a:1, b:1), b = "bbxx" (b:2, x:2). Surplus of a over b: a:+1 (b:−1 cancels). Only one change needed.

Example 3

Input: s = "abc"
Output: -1
Note: Odd length 3 — cannot split into two equal halves.

Constraints

1 ≤ |s| ≤ 10⁴
s consists of lowercase English letters only
A 'change' replaces one character with any other (no insert/delete)

Clarifying questions4First question: What happens on odd length?Explore questions

Q1.What happens on odd length?
Return −1. Two halves of different sizes can't be anagrams no matter how many changes you make.
Q2.Can I edit both halves?
No. The problem only asks to change characters in one half to match the other. Editing both is the related 'Making Anagrams' problem.
Q3.Is a change a replacement or a delete?
A replacement — swap a character for any other. Lengths stay equal, so deletes aren't involved.
Q4.What alphabet?
Lowercase a–z, so 26 integer counters suffice — O(1) extra space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

If the length is odd, the answer is −1 (you can't split into two equal halves). Otherwise split the string into halves a and b, count the character frequencies of each, and the minimum number of changes equals the sum of the positive surpluses of a over b — i.e. for every letter, how many more times it appears in a than in b. That equals (sum of absolute frequency differences) / 2. O(n) time, O(1) space (26 counters).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reduce 'make these anagrams' to a pure frequency-count problem, and whether you correctly count edits as surplus-in-one-half rather than double-counting both halves.

Where candidates slip

Summing the absolute differences without dividing by two (that's the Making Anagrams answer, where both strings can be edited), or forgetting the odd-length → −1 guard.

How to stand out

State that one replacement fixes one surplus-and-deficit pair simultaneously, so the answer is the surplus count, equivalently sum(|diff|)/2. Mention the fixed 26-array gives O(1) space.

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	Sort Each Half and Compare Letter Counts (Baseline)	`O(n log n)`	`O(n)`	Mention to show you understand 'anagram = same multiset', then note sorting is overkill versus counting.	Read
2	Single Frequency-Difference Pass (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — frame it as 'one histogram of (firstHalf − secondHalf), then sum the positives'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewString sLength even?NoYesExplore 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

Sort Each Half and Compare Letter Counts (Baseline)

TimeO(n log n)SpaceO(n)

Mention to show you understand 'anagram = same multiset', then note sorting is overkill versus counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Two strings are anagrams iff their sorted forms are identical. How could sorting help you measure the gap?

2Hint 2Explore hint

Sort both halves. Walk them together; every position where they disagree hints at a needed change — but sorting muddies the exact count.

3Hint 3Explore hint

Counting is cleaner: tally each half's letters and compare tallies directly instead of sorting.

A · Core idea

The definition of anagram is 'same characters with the same multiplicities'. A natural first instinct is to sort each half so equal multisets line up, then measure how far apart they are.

Why sorting feels right but is the long way around. Sorting groups identical letters together, so two anagrams become byte-identical after sorting. To count edits, though, you don't actually care about order at all — you care about how many of each letter each half holds. Sorting throws away nothing useful but adds a log-factor and forces you to re-derive counts by scanning runs.

Why we move on. The whole computation is a histogram comparison. A histogram is built in one O(n) pass with a 26-slot array; sorting is strictly more work for the same information. Open with this to prove you know the anagram definition, then replace it with frequency counting.

B · Visual dry run

Interactive dry run

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

s = "aaabbb"

Array state

half a

count a = {a:3}

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int anagram(String s) { int n = s.length(); if (n % 2 != 0) return -1; char[] a = s.substring(0, n / 2).toCharArray(); char[] b = s.substring(n / 2).toCharArray();Explore the full code

solution.javaJava

Sort Each Half and Compare Letter Counts (Baseline) — reference

3 teaching notes

1
public int anagram(String s) {
2
    int n = s.length();
3
    // Odd length can't split into equal halves — impossible.
4
    if (n % 2 != 0) return -1;
5
    char[] a = s.substring(0, n / 2).toCharArray();
6
    char[] b = s.substring(n / 2).toCharArray();
7
    // Sorting is the baseline crutch; it isn't needed once we count letters.
8
    Arrays.sort(a);
9
    Arrays.sort(b);
10
    int[] countA = new int[26];
11
    int[] countB = new int[26];
12
    for (char c : a) countA[c - 'a']++;
13
    for (char c : b) countB[c - 'a']++;
14
    int changes = 0;
15
    for (int i = 0; i < 26; i++) {
16
        // Sum only the surplus of a over b — each surplus is one replacement.
17
        if (countA[i] > countB[i]) changes += countA[i] - countB[i];
18
    }
19
    return changes;
20
}

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

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

Sorting and frequency-counting both reduce a string to its multiset of characters. Counting reaches that multiset in O(n) with O(1) space, so prefer it the moment you only need per-letter totals.

ComplexityO(n log n) time, O(n) space — Sorting each half of size n/2 costs O(n log n). The comparison is O(n). Sorted copies use O(n) space.

E · Edge cases and pitfalls5s = "" — Even length 0 → both halves empty → 0 changes.Explore edge cases

Edge cases handled

s = ""Even length 0 → both halves empty → 0 changes.
s = "ab"a = "a", b = "b". Surplus a:1 → 1 change.

Pitfalls

Sorting then comparing positions instead of counts — fragile for measuring edits.
Forgetting the odd-length −1 guard before slicing.
Paying O(n log n) when an O(n) histogram gives the same answer.

03.2

Approach 2 of 2 · Optimal

Single Frequency-Difference Pass (Optimal)

TimeO(n)SpaceO(1)

The answer they want — frame it as 'one histogram of (firstHalf − secondHalf), then sum the positives'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need order — you need per-letter counts. What single array tracks the balance between the two halves?

2Hint 2Explore hint

Use one int[26]: increment for each char in the first half, decrement for each char in the second half.

3Hint 3Explore hint

After the pass, every positive entry is a letter the first half has in surplus. Sum those positives — that's the minimum number of replacements.

A · Core idea

Maintain a single int[26] balance array. Walk the first half adding +1 to each letter's slot, then walk the second half subtracting 1. After both passes, slot c holds freq_a(c) − freq_b(c). The minimum number of changes is the sum of the positive slots.

Why positive slots are exactly the edit count. A positive value at letter c means the first half has that many more cs than the second half. To make the second half an anagram, each of those missing cs must be created by replacing some other character in the second half. Crucially, the surplus letters in a and the deficit letters in b come in matched pairs: every +1 somewhere is balanced by a −1 elsewhere, because both halves have the same length. So one replacement simultaneously removes a surplus and fills a deficit. Counting just the positives (or equivalently sum(|balance|)/2) avoids double-counting that single fix.

Why O(1) space. The alphabet is fixed at 26 letters, so the balance array never grows with n. That is the line to say aloud: 'O(n) time, O(1) space because the alphabet is constant.'

Why the odd guard comes first. If n is odd the halves differ in size and no number of replacements can equalise the multisets — return −1 before touching the array.

B · Visual dry run

Interactive dry run

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

s = "xaxbbbxx"

Array state

after add a

a="xaxb" → x:+2, a:+1, b:+1

x:+2

[0]

a:+1

[1]

b:+1

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Single Frequency-Difference Pass (Optimal) — optimal

4 teaching notes

1
public int anagram(String s) {
2
    int n = s.length();
3
    // Odd length is impossible — short-circuit before any counting.
4
    if (n % 2 != 0) return -1;
5
    int[] balance = new int[26];
6
    int half = n / 2;
7
    // First half contributes +1 per letter.
8
    for (int i = 0; i < half; i++) balance[s.charAt(i) - 'a']++;
9
    // Second half cancels with −1 per letter.
10
    for (int i = half; i < n; i++) balance[s.charAt(i) - 'a']--;
11
    int changes = 0;
12
    for (int c : balance) {
13
        // Each positive surplus is one forced replacement; deficits are already paid
14
        // for.
15
        if (c > 0) changes += c;
16
    }
17
    return changes;
18
}

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

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

Encoding 'first half minus second half' into one signed histogram turns a two-string comparison into a single sweep. The sum of positive surpluses equals sum(|diff|)/2; the /2 is the giveaway that one replacement heals both a surplus and a deficit at once — exactly what separates this from Making Anagrams.

ComplexityO(n) time, O(1) space — One pass over n characters with O(1) work each = O(n). A fixed 26-element array is O(1) extra space regardless of n.

E · Edge cases and pitfalls6s = "xyyx" — a="xy", b="yx" — identical multisets → balance all zero → 0 changes.Explore edge cases

Edge cases handled

s = "xyyx"a="xy", b="yx" — identical multisets → balance all zero → 0 changes.
s = "mnop"a="mn", b="op" — surplus m:+1, n:+1 → 2 changes.
s = "a"Odd length → −1.

Pitfalls

Summing |diff| without /2 — that overcounts because a surplus and its matching deficit are one fix.
Allocating a HashMap when a 26-int array is O(1) and faster.
Counting only one half and forgetting to subtract the other.

Practice

Try the solution yourself

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

Editable code previewpublic int anagram(String s) { int n = s.length(); if (n % 2 != 0) return -1; int[] balance = new int[26]; int half = n / 2;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.

Double-counting the difference

Each replacement fixes a surplus in one half AND the matching deficit in the other at the same time. Summing all |diffs| counts both ends of that single fix.

Explore the code comparison

Don't write this

return sum(abs(count_a[c] - count_b[c]) for c in set(a) | set(b))

Write this instead

return sum(max(0, count_a[c] - count_b[c]) for c in count_a)

Missing the odd-length guard

Slicing an odd string gives halves of size floor(n/2) and ceil(n/2); comparing them yields a wrong positive number instead of the required −1.

Explore the code comparison

Don't write this

char[] a = s.substring(0, n / 2).toCharArray();
char[] b = s.substring(n / 2).toCharArray();

Write this instead

if (n % 2 != 0) return -1;
char[] a = s.substring(0, n / 2).toCharArray();
char[] b = s.substring(n / 2).toCharArray();

Indexing the wrong second half

Off-by-one on the split sends the middle character to the wrong half, corrupting both counts.

Explore the code comparison

Don't write this

char[] b = s.substring(n / 2 + 1).toCharArray();

Write this instead

char[] b = s.substring(n / 2).toCharArray();

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency-difference of two halves

Code pattern to memorize

n = len(s)
if n is odd: return -1
a, b = s[:n/2], s[n/2:]
count = freq(a) - freq(b)   # per character
return sum(c for c in count if c > 0)   # == sum(|c|)/2

Rules to remember

1Odd length → immediately −1; halves of unequal size can never be anagrams.
2You only need to change characters in one half — count surplus letters in a, not both directions.
3Sum of positive differences equals sum(|diff|)/2 — each surplus in a pairs with a deficit in b.
426 fixed counters means O(1) space, not O(n) — say this out loud.
5Changing a character is one operation; you never delete or insert, only replace.

Use this pattern when

Two equal-length strings (or two halves) and you need edits to make them anagrams
The cost is defined per-character-replacement, not per-deletion
Order doesn't matter — only multiset of characters
Lowercase-only alphabet so a fixed 26-slot array works

Choose another pattern when

Deletions allowed from both strings → Making Anagrams (sum of all |diffs|, not /2)
You must check equality, not count edits → just compare sorted strings or frequency maps
Unicode / huge alphabet → use a hash map, not a 26-array
Substrings / sliding window of anagrams → that's a different (window) pattern

Interview takeaway

Replacing characters in one half to match the other costs exactly the number of surplus letters in that half. Because every surplus in `a` is mirrored by a deficit in `b`, summing positive differences (or `sum(|diff|)/2`) gives the answer in one frequency pass.

Continue

Transfer the pattern to another problem

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

Transferable patternFrequency-difference counting. Whenever a problem is about rearranging or replacing characters to reach an anagram, reduce each side to a 26-slot histogram and read the answer off the differences. Counting how many edits = sum of positive surpluses; counting deletions across both strings = sum of all absolute differences.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Making Anagrams
Two separate strings, deletions allowed from both — answer is sum of ALL |diffs|, no /2.
Valid Anagram
Just decide YES/NO — one frequency map, check it returns to all zeros.
Group Anagrams
Bucket by the sorted (or count-tuple) signature of each word.
Find All Anagrams in a String
Coming soon
Sliding window of fixed size with a running frequency match.

Same pattern

←

The Full Counting Sort

Continue · Next problem

HackerRank in a String

easyStrings0Sometimes asked

Anagram

Arrays & Hashing · 62 of 83 · 7 min

If the length of s is odd, the two halves cannot have equal length, so it is impossible — return -1.

In plain English

Examples

Example 1

Input: s = "aaabbb"
Output: 3
Note: a = "aaa", b = "bbb". The first half has 3 surplus 'a's that the second half lacks, so all 3 'b's must become 'a's. 3 changes.

Example 2

Input: s = "xaxbbbxx"
Output: 1
Note: a = "xaxb" (x:2, a:1, b:1), b = "bbxx" (b:2, x:2). Surplus of a over b: a:+1 (b:−1 cancels). Only one change needed.

Example 3

Input: s = "abc"
Output: -1
Note: Odd length 3 — cannot split into two equal halves.

Constraints

1 ≤ |s| ≤ 10⁴
s consists of lowercase English letters only
A 'change' replaces one character with any other (no insert/delete)

Clarifying questions4First question: What happens on odd length?Explore questions

Q1.What happens on odd length?
Return −1. Two halves of different sizes can't be anagrams no matter how many changes you make.
Q2.Can I edit both halves?
No. The problem only asks to change characters in one half to match the other. Editing both is the related 'Making Anagrams' problem.
Q3.Is a change a replacement or a delete?
A replacement — swap a character for any other. Lengths stay equal, so deletes aren't involved.
Q4.What alphabet?
Lowercase a–z, so 26 integer counters suffice — O(1) extra space.

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 reduce 'make these anagrams' to a pure frequency-count problem, and whether you correctly count edits as surplus-in-one-half rather than double-counting both halves.

Where candidates slip

Summing the absolute differences without dividing by two (that's the Making Anagrams answer, where both strings can be edited), or forgetting the odd-length → −1 guard.

How to stand out

State that one replacement fixes one surplus-and-deficit pair simultaneously, so the answer is the surplus count, equivalently sum(|diff|)/2. Mention the fixed 26-array gives O(1) space.

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	Sort Each Half and Compare Letter Counts (Baseline)	`O(n log n)`	`O(n)`	Mention to show you understand 'anagram = same multiset', then note sorting is overkill versus counting.	Read
2	Single Frequency-Difference Pass (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want — frame it as 'one histogram of (firstHalf − secondHalf), then sum the positives'.	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

Sort Each Half and Compare Letter Counts (Baseline)

TimeO(n log n)SpaceO(n)

Mention to show you understand 'anagram = same multiset', then note sorting is overkill versus counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Two strings are anagrams iff their sorted forms are identical. How could sorting help you measure the gap?

2Hint 2Explore hint

Sort both halves. Walk them together; every position where they disagree hints at a needed change — but sorting muddies the exact count.

3Hint 3Explore hint

Counting is cleaner: tally each half's letters and compare tallies directly instead of sorting.

A · Core idea

The definition of anagram is 'same characters with the same multiplicities'. A natural first instinct is to sort each half so equal multisets line up, then measure how far apart they are.

B · Visual dry run

Interactive dry run

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

s = "aaabbb"

Array state

half a

count a = {a:3}

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Sort Each Half and Compare Letter Counts (Baseline) — reference

3 teaching notes

1
public int anagram(String s) {
2
    int n = s.length();
3
    // Odd length can't split into equal halves — impossible.
4
    if (n % 2 != 0) return -1;
5
    char[] a = s.substring(0, n / 2).toCharArray();
6
    char[] b = s.substring(n / 2).toCharArray();
7
    // Sorting is the baseline crutch; it isn't needed once we count letters.
8
    Arrays.sort(a);
9
    Arrays.sort(b);
10
    int[] countA = new int[26];
11
    int[] countB = new int[26];
12
    for (char c : a) countA[c - 'a']++;
13
    for (char c : b) countB[c - 'a']++;
14
    int changes = 0;
15
    for (int i = 0; i < 26; i++) {
16
        // Sum only the surplus of a over b — each surplus is one replacement.
17
        if (countA[i] > countB[i]) changes += countA[i] - countB[i];
18
    }
19
    return changes;
20
}

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

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

Sorting and frequency-counting both reduce a string to its multiset of characters. Counting reaches that multiset in O(n) with O(1) space, so prefer it the moment you only need per-letter totals.

ComplexityO(n log n) time, O(n) space — Sorting each half of size n/2 costs O(n log n). The comparison is O(n). Sorted copies use O(n) space.

E · Edge cases and pitfalls5s = "" — Even length 0 → both halves empty → 0 changes.Explore edge cases

Edge cases handled

s = ""Even length 0 → both halves empty → 0 changes.
s = "ab"a = "a", b = "b". Surplus a:1 → 1 change.

Pitfalls

Sorting then comparing positions instead of counts — fragile for measuring edits.
Forgetting the odd-length −1 guard before slicing.
Paying O(n log n) when an O(n) histogram gives the same answer.

03.2

Approach 2 of 2 · Optimal

Single Frequency-Difference Pass (Optimal)

TimeO(n)SpaceO(1)

The answer they want — frame it as 'one histogram of (firstHalf − secondHalf), then sum the positives'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need order — you need per-letter counts. What single array tracks the balance between the two halves?

2Hint 2Explore hint

Use one int[26]: increment for each char in the first half, decrement for each char in the second half.

3Hint 3Explore hint

After the pass, every positive entry is a letter the first half has in surplus. Sum those positives — that's the minimum number of replacements.

A · Core idea

Why O(1) space. The alphabet is fixed at 26 letters, so the balance array never grows with n. That is the line to say aloud: 'O(n) time, O(1) space because the alphabet is constant.'

Why the odd guard comes first. If n is odd the halves differ in size and no number of replacements can equalise the multisets — return −1 before touching the array.

B · Visual dry run

Interactive dry run

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

s = "xaxbbbxx"

Array state

after add a

a="xaxb" → x:+2, a:+1, b:+1

x:+2

[0]

a:+1

[1]

b:+1

[2]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Single Frequency-Difference Pass (Optimal) — optimal

4 teaching notes

1
public int anagram(String s) {
2
    int n = s.length();
3
    // Odd length is impossible — short-circuit before any counting.
4
    if (n % 2 != 0) return -1;
5
    int[] balance = new int[26];
6
    int half = n / 2;
7
    // First half contributes +1 per letter.
8
    for (int i = 0; i < half; i++) balance[s.charAt(i) - 'a']++;
9
    // Second half cancels with −1 per letter.
10
    for (int i = half; i < n; i++) balance[s.charAt(i) - 'a']--;
11
    int changes = 0;
12
    for (int c : balance) {
13
        // Each positive surplus is one forced replacement; deficits are already paid
14
        // for.
15
        if (c > 0) changes += c;
16
    }
17
    return changes;
18
}

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

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

ComplexityO(n) time, O(1) space — One pass over n characters with O(1) work each = O(n). A fixed 26-element array is O(1) extra space regardless of n.

E · Edge cases and pitfalls6s = "xyyx" — a="xy", b="yx" — identical multisets → balance all zero → 0 changes.Explore edge cases

Edge cases handled

s = "xyyx"a="xy", b="yx" — identical multisets → balance all zero → 0 changes.
s = "mnop"a="mn", b="op" — surplus m:+1, n:+1 → 2 changes.
s = "a"Odd length → −1.

Pitfalls

Summing |diff| without /2 — that overcounts because a surplus and its matching deficit are one fix.
Allocating a HashMap when a 26-int array is O(1) and faster.
Counting only one half and forgetting to subtract the other.

Practice

Try the solution yourself

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

Editable code previewpublic int anagram(String s) { int n = s.length(); if (n % 2 != 0) return -1; int[] balance = new int[26]; int half = n / 2;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.

Double-counting the difference

Each replacement fixes a surplus in one half AND the matching deficit in the other at the same time. Summing all |diffs| counts both ends of that single fix.

Explore the code comparison

Don't write this

return sum(abs(count_a[c] - count_b[c]) for c in set(a) | set(b))

Write this instead

return sum(max(0, count_a[c] - count_b[c]) for c in count_a)

Missing the odd-length guard

Slicing an odd string gives halves of size floor(n/2) and ceil(n/2); comparing them yields a wrong positive number instead of the required −1.

Explore the code comparison

Don't write this

char[] a = s.substring(0, n / 2).toCharArray();
char[] b = s.substring(n / 2).toCharArray();

Write this instead

if (n % 2 != 0) return -1;
char[] a = s.substring(0, n / 2).toCharArray();
char[] b = s.substring(n / 2).toCharArray();

Indexing the wrong second half

Off-by-one on the split sends the middle character to the wrong half, corrupting both counts.

Explore the code comparison

Don't write this

char[] b = s.substring(n / 2 + 1).toCharArray();

Write this instead

char[] b = s.substring(n / 2).toCharArray();

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency-difference of two halves

Code pattern to memorize

n = len(s)
if n is odd: return -1
a, b = s[:n/2], s[n/2:]
count = freq(a) - freq(b)   # per character
return sum(c for c in count if c > 0)   # == sum(|c|)/2

Rules to remember

1Odd length → immediately −1; halves of unequal size can never be anagrams.
2You only need to change characters in one half — count surplus letters in a, not both directions.
3Sum of positive differences equals sum(|diff|)/2 — each surplus in a pairs with a deficit in b.
426 fixed counters means O(1) space, not O(n) — say this out loud.
5Changing a character is one operation; you never delete or insert, only replace.

Use this pattern when

Two equal-length strings (or two halves) and you need edits to make them anagrams
The cost is defined per-character-replacement, not per-deletion
Order doesn't matter — only multiset of characters
Lowercase-only alphabet so a fixed 26-slot array works

Choose another pattern when

Deletions allowed from both strings → Making Anagrams (sum of all |diffs|, not /2)
You must check equality, not count edits → just compare sorted strings or frequency maps
Unicode / huge alphabet → use a hash map, not a 26-array
Substrings / sliding window of anagrams → that's a different (window) pattern

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

Making Anagrams
Two separate strings, deletions allowed from both — answer is sum of ALL |diffs|, no /2.
Valid Anagram
Just decide YES/NO — one frequency map, check it returns to all zeros.
Group Anagrams
Bucket by the sorted (or count-tuple) signature of each word.
Find All Anagrams in a String
Coming soon
Sliding window of fixed size with a running frequency match.

Same pattern

←

The Full Counting Sort

Continue · Next problem

HackerRank in a String