A catalog ingest treated two SKUs as the same product if they used the same letters. The first version sorted both copies and compared. A few thousand codes overnight returned in seconds. A million-row Sunday dump was still allocating two char arrays when the window closed.

Valid Anagram asks whether two strings use the same characters at the same frequencies. s.charAt(i) is already free. Sorting both copies uses that and still pays O(n log n) plus two rewrites. A 26-slot count answers in linear time without permuting either string.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about matching frequencies so an anagram is a count, not a sort.

The problem

Given two strings s and t, return true if t is an anagram of s — the same characters with the same frequencies, in any order — and false otherwise. Assume lowercase English letters unless a follow-up widens the alphabet.

s = "anagram", t = "nagaram"  →  true
s = "rat",     t = "car"      →  false
s = "ab",      t = "a"        →  false   lengths differ

Note: Sort both copies, then Arrays.equals, is a legal middle path. It is not the usual interview answer: the prompt did not ask you to rewrite two arrays, and a count answers in linear time without that permute.

Sorting both copies is the honest brute force

Copy each string to a char array, sort, compare. Correct. O(n log n), and it allocates two rewrites.

boolean isAnagramSorted(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);
}

At n = 20 this is a rounding error. At n in the hundreds of thousands you paid two sorts for a question a count answers in linear time: do the letter frequencies match?

One array: increment, then decrement

If the lengths differ, return false immediately. Otherwise allocate 26 ints.

  • Increment count[c - 'a'] for every character in s.
  • Decrement the same slots for every character in t.
  • Any leftover nonzero means a frequency missed.

You never sort. You never rewrite s or t. Once the lengths match you can fuse both walks into one loop — that is the Java below. A HashMap is the same idea when the alphabet is not 26 letters.

s = "anagram"   t = "nagaram"

len 7 == 7
after s:  a:3 n:1 g:1 r:1 m:1
t: n→0  a→2  g→0  a→1  r→0  a→0  m→0
scan count: all zero → true

The Java is that walk:

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']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int n : count) {
        if (n != 0) {
            return false;
        }
    }
    return true;
}

Time is O(n) — one pass over both strings, then a 26-slot scan. Space is O(1) for the fixed alphabet. A map would pay extra space if the follow-up opens Unicode; that layout is the hash-table post, not this board.

Note: Check lengths first. A paired loop over s.length() never sees extra characters in a longer t. The early false is correctness, not a micro-optimization.

What interviewers usually poke next

  • Unicode, not just a–z. The 26-slot array is a lie. Use a map, same increment/decrement, unbounded keys.
  • Group Anagrams. Grouping many strings is the same signature, many times. This post only asks yes or no for one pair.
  • Two empty strings. Length 0 equals 0, the count stays zero, return true. Do not invent a special case unless they ask.
  • Mutation allowed. Sort the copies you allocated. Extra space sits in those arrays, time is O(n log n), and you should say why the count is still the default when they did not ask you to reorder.

You are done with this problem when you can say, out loud, why sorting both copies is correct, why a 26-slot count is enough for lowercase English, and why a length mismatch is an early false rather than a later scan.