242. Valid Anagram

Two strings are anagrams when they’re the same multiset of characters, possibly reordered (identical strings count too) — so the whole problem is really “do these two strings have identical letter counts?” That reframing is the point, and it’s a core move in the arrays and hashing pattern: turn a comparison into a counting problem a table can answer.

The problem

Given two strings s and t, decide whether t is a rearrangement of s using every letter exactly as many times. (Full statement on LeetCode.)

"listen" and "silent" are anagrams. "tea" and "eat" are too. But "rat" and "car" aren’t — both have three letters, yet the counts don’t line up.

Intuition: anagrams have identical letter histograms

Ordering is noise here. If you build a histogram of each string — how many as, how many bs, and so on — two anagrams produce the exact same histogram, and two non-anagrams differ in at least one bucket. So the question collapses to: are the two histograms equal?

Sorting both strings and comparing is one honest way to do it, and it’s fine to mention: $O(n \log n)$ time, a couple of lines. But you don’t need a total order over the letters, only the counts. Counting is $O(n)$, and with lowercase-only input the “histogram” is just a fixed 26-slot array — no hash map, constant space.

The tidy trick is to use one array instead of two. Walk s and increment; walk t and decrement. If every bucket lands back at zero, each letter that s added t took away in equal measure, which is exactly the anagram condition.

Solution

class Solution {
    public boolean isAnagram(String s, String t) {
        // Different lengths can't be anagrams — bail early.
        if (s.length() != t.length()) return false;

        // One histogram: s adds, t subtracts.
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;   // same index i, both strings equal length
        }

        // Any nonzero bucket means the letter counts didn't match.
        for (int c : count) {
            if (c != 0) return false;
        }
        return true;
    }
}

The length guard isn’t just an optimization — it’s what lets the single loop walk both strings at index i safely. s.charAt(i) - 'a' maps 'a'..'z' to 0..25, so the array is a direct-address table with no hashing overhead.

If the interviewer opens the input up to arbitrary Unicode (the problem’s follow-up), the 26-slot array stops working — and so does HashMap<Character, Integer>, because a Java char is a UTF-16 code unit, so characters outside the Basic Multilingual Plane split into surrogate pairs and two different strings can share a code-unit histogram. Iterate with String.codePoints() into a HashMap<Integer, Integer> instead, and the same add-then-check-zero logic carries over at $O(1)$ average per code point.

Complexity

Approach	Time	Space
Sort and compare	$O(n \log n)$	$O(1)$–$O(n)$
Frequency count	$O(n)$	$O(1)$

The count array holds 26 ints no matter how long the strings get, so its space is constant. For the Unicode variant the map grows with the number of distinct characters, making space $O(k)$ for a k-letter alphabet.

In an interview

Say the reframing out loud first: “anagrams are the same letters in a different order, so I just need to compare character counts.” That signals you saw past the string manipulation to the counting problem. Offer sorting as the baseline, then upgrade to the $O(n)$ count — the same trade you’d make anywhere you can replace a sort with a bucket.

The trap is assuming lowercase ASCII when it wasn’t stated. Ask about the character set before you commit to int[26]: uppercase, spaces, and Unicode all break the fixed array, and naming that constraint is half of what’s being graded. This “count with a hash table” reflex is the backbone of the arrays and hashing pattern — it’s the same tool behind Group Anagrams, where the sorted-letter signature becomes a map key, and Top K Frequent Elements, which counts first and ranks second.

References

• LeetCode 242 — Valid Anagram