Hashing — Valid Anagram
↗ LeetCode: Valid Anagram · Easy · pattern chapter →
Given two strings s and t, return true iff t is an anagram of s.
Example 1 — s = "anagram", t = "nagaram" → trueExample 2 — s = "rat", t = "car" → falseExample 3 — s = "aa", t = "a" → false (different lengths)
Constraints — 1 ≤ n ≤ 5 · 10⁴. Lowercase English. Brute sort both then compare is O(n log n) = 10⁵·17 ≈ 2·10⁶ ops at n=10⁵. Frequency array of 26 chars is O(n) = 10⁵ ops with O(1) alphabet space.
Interview timer00:00
Approach 1 — Sort both and compare
Intuition. Two strings are anagrams iff their sorted forms are equal.
boolean isAnagramSort(String s, String t) {
if (s.length() != t.length()) return false;
char[] a = s.toCharArray(); Arrays.sort(a);
char[] b = t.toCharArray(); Arrays.sort(b);
return Arrays.equals(a, b);
}Complexity — Time O(n log n); Space O(n).
Approach 2 — Frequency array (ASCII)
Insight from sort. We don't need order — just multi-set equality. Increment on s, decrement on t; verify all zeros.
boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
cnt[t.charAt(i) - 'a']--;
}
for (int c : cnt) if (c != 0) return false;
return true;
}Complexity — Time O(n); Space O(1) (26 buckets).
Approach 3 — Unicode-safe: HashMap
Insight from ASCII. If s, t may contain Unicode (surrogate pairs etc.), use codePoints() and a HashMap.
boolean isAnagramUnicode(String s, String t) {
if (s.codePointCount(0, s.length()) != t.codePointCount(0, t.length())) return false;
Map<Integer, Integer> cnt = new HashMap<>();
s.codePoints().forEach(c -> cnt.merge(c, 1, Integer::sum));
t.codePoints().forEach(c -> cnt.merge(c, -1, Integer::sum));
for (int v : cnt.values()) if (v != 0) return false;
return true;
}Complexity — Time O(n); Space O(σ) where σ ≤ n.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Sort both | O(n log n) | O(n) | baseline |
| Frequency array (ASCII) | O(n) | O(1) | expected optimum |
| HashMap (Unicode) | O(n) | O(σ) | generalization |
When to use which
- Lowercase English →
int[26]frequency array. - General ASCII →
int[128]orint[256]. - Unicode / emoji → HashMap over code points.
- Stream / can't materialize
t→ maintain running count ofsfirst, then decrement astarrives; return false early on any negative overshoot.
Related problems
- Find All Anagrams in a String — sliding window
- Group Anagrams — canonical-key hashing
- Permutation in String — sliding boolean version