Valid Anagram

1. Problem & Core Objective

The problem

Given two strings s and t, return true if t is an anagram of s — that is, if t uses exactly the same letters as s, the same number of times, in any order.

Input:  s = "anagram", t = "nagaram"    Output: true
Input:  s = "rat",     t = "car"        Output: false
Input:  s = "a",       t = "ab"         Output: false    (different lengths)

Constraints:

• 1 <= s.length, t.length <= 5 * 10^4
• s and t consist of lowercase English letters

What the interviewer is actually testing

Three things, in increasing order of what separates candidates:

1. Can you restate "anagram" precisely? It means equal multisets of characters. Order is irrelevant; multiplicity is not. "aab" and "abb" are not anagrams even though they use the same letter set.
2. Do you notice the bounded alphabet? The constraint says lowercase English letters — 26 possibilities. That single line is the difference between an O(n)-space solution and an O(1)-space one.
3. Do you handle the length check first? Different lengths can never be anagrams, and testing it up front is a free O(1) rejection.

The constraint line is the question. A candidate who reads "lowercase English letters" and reaches for a HashMap anyway has missed the signal deliberately planted for them.

2. First-Principles Thought Process

Step 1 — Translate the word into a data structure

"Anagram" is an English word. Turn it into something mechanical:

Two strings are anagrams iff they have identical character counts.

Once phrased that way, the algorithm is obvious: count the characters in each, compare the counts.

Step 2 — Read the constraints

n up to 5 × 10^4, so O(n) and O(n log n) are both comfortably fine. No pressure from the length.

But the alphabet constraint is the interesting one:

"s and t consist of lowercase English letters."

That means only 26 distinct characters can ever appear. So instead of a HashMap<Character, Integer> — which allocates objects, hashes keys, and grows — you can use a plain int[26], indexed by c - 'a'.

That's not just faster. It changes the space complexity to O(1), because 26 is a constant fixed by the problem, not a function of the input.

Step 3 — Realize you need only one array, not two

The naive version builds two count arrays and compares them. But notice:

If s and t have identical counts, then adding for s and subtracting for t leaves every slot at zero.

So one array suffices: increment while scanning s, decrement while scanning t, then verify everything is zero. Half the memory, and the comparison becomes "is it all zeros" instead of an array equality check.

Step 4 — The free early exit

If s.length() != t.length(), they cannot be anagrams — one has more characters than the other. That's an O(1) check, and it also makes the single-array logic airtight: with equal lengths, "all counts zero" is exactly equivalent to "same multiset."

3. Solution Paths

Approach 1 — Sort both strings and compare

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    char[] a = s.toCharArray();
    char[] b = t.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);

    return Arrays.equals(a, b);
}

How it works. Sorting puts both strings into a canonical form — anagrams sort to the identical character sequence. "anagram" and "nagaram" both become "aaagmnr".

• Time: O(n log n) — the two sorts dominate.
• Space: O(n) for the two char arrays.

This is a perfectly acceptable answer and the fastest one to write. Its virtue is that it needs no insight — "canonical form" generalizes to Group Anagrams.

Its weakness is the unnecessary log n factor: you're producing a full ordering when you only need counts.

Counter-questions on this approach

⭐ "Why sort, when what you actually need is counts?"

Sorting gives a total ordering of the characters; an anagram check only needs a multiset comparison, which is strictly weaker. I'm paying a log n factor for information I immediately throw away. Its one virtue is that it makes no assumption about the alphabet.

"You allocate two char[] copies — that's O(n) space."

Correct, and the count-array version is O(1). Strings are immutable in Java, so there's no in-place sort available; the copies are unavoidable for this approach.

Approach 2 — HashMap of counts

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    Map<Character, Integer> count = new HashMap<>();
    for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);

    for (char c : t.toCharArray()) {
        Integer cur = count.get(c);
        if (cur == null || cur == 0) return false;      // t has a char s doesn't (enough of)
        count.put(c, cur - 1);
    }
    return true;
}

How it works. Count everything in s, then walk t decrementing. If t ever needs a character that's exhausted or absent, they aren't anagrams.

Because the lengths are equal and every character of t was successfully matched, no final zero-check is needed.

• Time: O(n).
• Space: O(k) where k is the number of distinct characters — here at most 26, so effectively O(1), but the structure is sized by the alphabet.

When this is the right answer: when the alphabet is not bounded — Unicode, arbitrary bytes, words instead of characters. That's the standard follow-up.

Counter-questions on this approach

⭐ "The problem guarantees lowercase English letters. Why reach for a HashMap?"

I shouldn't, given that constraint — a map is the right choice only when the key space is large or unknown. Here it's fixed at 26, so an array is the specialized form of the same idea: a perfect, collision-free hash that costs nothing to compute. The map version also makes space O(k) instead of O(1).

"Do you need a final zero-check here, like the array version has?"

No. The lengths are equal and every character of t was successfully matched and decremented, so nothing can be left over. The check is only needed when you count both strings independently.

Approach 3 — Fixed count array (optimal)

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;      // add for s
        count[t.charAt(i) - 'a']--;      // subtract for t
    }

    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

How it works. Since the lengths are equal, one loop can process both strings at once — incrementing for s and decrementing for t at the same index. If the multisets match, every counter cancels to zero.

Trace on s = "anagram", t = "nagaram":

All zeros → anagram. ✓

Trace on s = "rat", t = "car":

Final: c = -1, t = +1, rest 0 → not all zero → false. ✓

• Time: O(n) — one pass over both strings, plus a fixed 26-step check.
• Space: O(1) — 26 ints regardless of input size.

Why count[c - 'a'] works. Characters in Java are numeric codes: 'a' is 97, 'b' is 98. So c - 'a' maps 'a'→0, 'b'→1, …, 'z'→25 — a perfect index into a 26-slot array. See 03.

Counter-questions on this approach

⭐ "You claim O(1) space, but you allocated an array."

26 is a constant fixed by the problem, not a function of the input. A 5-character string and a 50,000-character string both use exactly 26 ints — the array doesn't grow with n. If the alphabet size were an input parameter k, it would be O(k).

⭐ "Is the length check actually necessary, or is it decoration?"

Necessary for this version specifically: the single loop indexes s and t at the same i, which requires equal lengths or it throws. It's also a free O(1) rejection that makes the intent explicit.

"Why one array rather than two?"

If the counts match, incrementing for s and decrementing for t cancels every slot to zero. Half the memory, and the final test becomes "is it all zeros" instead of an array comparison.

"Could you avoid the final 26-element scan entirely?"

Yes — carry a mismatches counter alongside, incrementing when a slot moves away from zero and decrementing when it returns, then answer mismatches == 0. Same complexity; it's the same incremental-invariant technique used in Permutation in String.

"What happens the moment the input isn't lowercase a–z?"

c - 'a' produces a negative or out-of-range index and it throws. For ASCII I'd widen to int[128] and index by the character directly; for Unicode I'd use a HashMap and iterate codePoints().

Comparison

4. Why the Optimal Wins

Against sorting. Sorting computes a total ordering of the characters. The question only needs how many of each — a strictly weaker fact. You're paying a log n factor for information you discard. Whenever you notice a solution producing more than the question asks for, there's usually a cheaper one.

Against the HashMap. Functionally identical, but every operation costs more: hash the Character, find the bucket, possibly resize, and box each int into an Integer. An array index is a single memory offset. Same big-O, several times faster in practice, and O(1) space instead of O(k).

The deeper point — and the one worth saying aloud:

"A HashMap is for when the key space is large or unknown. When the problem tells you the key space is small and fixed, an array is the specialized version of the same idea — a hash map with a perfect, collision-free hash function that costs nothing to compute."

That framing shows you understand int[26] isn't a trick; it's the degenerate case of hashing.

Why O(n) is the floor. You must read every character of both strings — skipping one lets an adversary put the mismatch there. So O(n) time is optimal, and O(1) space is optimal given the bounded alphabet.

5. Java Prerequisites

Characters are numbers

int idx = c - 'a';                 // 'a'->0, 'b'->1, ... 'z'->25
char c = (char) ('a' + idx);       // back again — the cast is REQUIRED

The cast is needed because 'a' + idx promotes to int, and Java won't narrow implicitly.

For uppercase or mixed case:

count[Character.toLowerCase(c) - 'a']++;      // normalize first
int[] count = new int[128];                    // or index by ASCII directly
count[c]++;

charAt vs toCharArray

for (int i = 0; i < s.length(); i++) s.charAt(i);   // no allocation
for (char c : s.toCharArray()) { }                  // allocates an O(n) copy

toCharArray is more readable; charAt avoids the copy. Here charAt is the better choice because you're indexing both strings at the same position anyway.

length vs length() vs size()

Map.merge for counting

count.merge(c, 1, Integer::sum);

Reads as: "if c is absent, store 1; if present, combine the old value with 1 using addition." See 02 §1.3.

Comparing arrays

Arrays.equals(a, b);               // element-by-element, 1-D
a == b                             // reference identity — almost never what you want

6. Interview Communication Guide

Clarifying questions

1. "Is the input restricted to lowercase English letters?" — the question here. The answer decides between int[26] and a HashMap.
2. "Should the comparison be case-sensitive?" — is "Rat" an anagram of "tar"?
3. "Can there be spaces or punctuation, and do they count?" — matters for real anagram phrases like "listen" / "silent".
4. "Can the strings be empty?" — two empty strings are anagrams by convention; confirm.
5. "Could these be Unicode?" — leads straight to the follow-up.

The pitch

"An anagram means the two strings have identical character counts — order doesn't matter, multiplicity does.

First, if the lengths differ they can't be anagrams, so that's a free O(1) rejection.

The simplest approach is to sort both and compare, O(n log n). But I don't actually need an ordering — I only need counts. And since the constraints say lowercase English letters, there are only 26 possible characters, so I can use an int[26] instead of a hash map.

Even better, because the lengths are equal I can do it in one pass: increment for s and decrement for t at the same index. If they're anagrams every counter cancels to zero.

That's O(n) time and O(1) space — 26 ints regardless of input size."

Edge cases to raise proactively

"aab" vs "abb" is the edge case to volunteer. It's the one that catches solutions using a Set instead of counts — they'd see {a,b} on both sides and wrongly return true. Mentioning it proves you understood "multiset", not just "set".

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if the inputs are Unicode?"

int[26] breaks — Unicode has over a million code points. Switch to HashMap<Character, Integer>: O(n) time, O(k) space in the distinct characters present.

There's a subtlety worth raising: Java char is 16 bits, so characters outside the Basic Multilingual Plane (emoji, rare scripts) are stored as two chars — a surrogate pair. Iterating by char would split them. The correct fix is s.codePoints(), which yields whole code points as ints.

"What if you had to check many strings pairwise for anagram-ness?"

Don't compare pairs. Compute a canonical key per string — sorted characters, or the count signature — and group by it. That's exactly Group Anagrams, and it turns O(n²) comparisons into O(n) hashing.

"What if you can't use extra space at all?"

Sorting in place — but strings are immutable in Java, so you'd need a char[] copy anyway. Genuinely O(1) extra space isn't achievable without mutating the input.

"What about anagrams ignoring spaces and case?"

Normalize while counting: skip non-letters, lowercase everything, and compare only the letter counts. The length pre-check no longer applies, so you need the full final zero-check.