Check if Two Strings Are Anagrams — Sort vs Frequency Counter in Java

Two main approaches

1. Frequency counter (preferred)

• Check lengths first; if different, false
• Array int[26] for lowercase ASCII (or int[128])
• For each char in s: increment; for each in t: decrement
• If all counts zero at end: anagram
• Time O(n), Space O(1) for ASCII

2. Sort and compare

• Sort both char arrays, compare
• Simpler, but O(n log n) time, O(n) space
• Acceptable for short strings

Always start with length check

• O(1) shortcut
• If lengths differ, return false immediately

Alphabet choices

ASCII lowercase

• int[26]
• s.charAt(i) - 'a'
• O(1) space
• Fastest

Full ASCII

• int[128]
• s.charAt(i) as index
• O(1) space

Unicode

• HashMap<Character, Integer>
• O(Σ) space (distinct chars)
• Slower due to hashing

Surrogate pairs (emoji)

• s.length() counts char units, not code points
• Iterate via s.codePoints() for full Unicode support
• Rare in interviews but real in production

Normalization (production)

• Case sensitivity: .toLowerCase() if ignoring case
• Whitespace: .replaceAll("\\s+", "") if ignoring spaces
• Punctuation: .replaceAll("\\p{Punct}", "")
• Diacritics: Normalizer.NFD + strip marks
• Decide based on spec

Edge cases

Empty strings

• "" and "": trivially anagrams (spec-dependent)
• "" and "a": length differs, false

Single character

• "a" and "a": true
• "a" and "b": false

Case sensitivity

• 'Listen' and 'Silent': case-sensitive false, case-insensitive true
• Clarify with interviewer

Whitespace

• 'a b c' and 'c b a': false if whitespace matters
• Typical anagram problems ignore whitespace

Null

• Throw or return false; decide and document

Variants

Group anagrams

• Given array of strings, group anagrams together
• Key: sorted string (O(k log k)) or frequency tuple (O(k))
• Frequency tuple is faster for long strings
• Store in HashMap<String, List>

Find all anagrams of p in s

• Sliding window of size |p|
• Maintain frequency array
• Arrays.equals on int[26] is O(1) — effectively O(n) total

Valid anagram with frequencies

• Two multisets equal
• Same technique

Isomorphic strings (different concept)

• Characters map 1:1
• 'egg' and 'add' are isomorphic, not anagrams
• Different constraint

Common pitfalls

1. Not checking lengths first

• Unnecessary O(n) work

2. Using sort when frequency is O(n)

• Sort is O(n log n) — worse for long strings

3. Assuming ASCII when input is Unicode

• int[26] fails for non-letter
• Use HashMap

4. Surrogate pair bugs

• Emoji / rare chars use two char units
• Use codePoints() for safety

5. Ignoring case when required

• Clarify with interviewer
• Add .toLowerCase() if case-insensitive

6. Not handling whitespace / punctuation

• Normalize first in production

For interviews

• Recommend frequency counter with int[26]
• Start with length check
• Mention sort as simpler alternative
• Address Unicode if input is general
• Extend to group-anagrams if asked

Recommendation: For checking if two strings are anagrams, the frequency counter approach is the canonical interview answer — O(n) time, O(1) space for ASCII (with int[26]), linear and cache-friendly. Always start with a length check (O(1) shortcut for mismatches). Use int[26] for lowercase letters, int[128] for full ASCII, or a HashMap for Unicode. For surrogate pairs (emoji, rare characters), iterate via codePoints() since char is 16-bit and can't hold all code points. Mention the sort-and-compare approach as simpler (4 lines) but O(n log n) and O(n) space — slower for long strings. For variants: group anagrams uses either a sorted string or a frequency tuple as a HashMap key; the frequency tuple is O(k) per key, faster for long strings. Find all anagrams of a pattern in a string uses a sliding window of size |p| with frequency matching. Always normalize according to spec: lowercase, strip whitespace, punctuation, and diacritics depending on the problem definition. Know the difference from isomorphic strings (1:1 character mapping, different constraint). The mental model: anagram check = equal frequency distributions; frequency counter makes this O(n) linear; length check is the cheap first gate. Once you've internalized the int[26] pattern, many string-frequency problems use the same template.