#242 Valid Anagram
frequently reported atBloombergInfosysTCSAmazonMicrosoftOracle
the problem
In plain words
Return true if t is an anagram of s — the same letters with the same counts, in any order.
in s = "anagram", t = "nagaram"
out true
in s = "rat", t = "car"
out false
- 1 ≤ s.length, t.length ≤ 5·10⁴
- Lowercase English letters only
- Follow-up: what if inputs contain Unicode?
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFrequency counting
Order doesn't matter, only counts. Count with s, un-count with t; anagrams cancel out exactly.
solutions
From brute force to optimal
Anagrams become identical once sorted.
- Different lengths → false.
- Sort both char arrays.
- Arrays.equals.
Sorting dominates.
toCharArray copies (Strings are immutable).
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; char[] a = s.toCharArray(), b = t.toCharArray(); Arrays.sort(a); Arrays.sort(b); return Arrays.equals(a, b); }}count[c − 'a']++ for s, -- for t; any negative means t has an extra letter.
- Different lengths → false.
- Count s.
- Decrement for t; if a count goes below 0 → false.
- Otherwise true.
One pass over each string.
26 counters regardless of input size.
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] count = new int[26]; // one slot per letter 'a'..'z' for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++; for (int i = 0; i < t.length(); i++) { if (--count[t.charAt(i) - 'a'] < 0) return false; // t has an extra letter } return true; // equal lengths + nothing negative => all zero }}Dry run
Same counting idea with a map, so any character works.
- merge(cp, 1, Integer::sum) for s.
- Decrement for t; fail on a negative.
- All counts must be zero.
O(1) average per map update.
k = number of distinct characters.
class Solution { /** Follow-up: any Unicode text. Counts code points, so emoji and accents work too. */ public boolean isAnagram(String s, String t) { Map<Integer, Integer> count = new HashMap<>(); s.codePoints().forEach(cp -> count.merge(cp, 1, Integer::sum)); for (int cp : t.codePoints().toArray()) { int left = count.getOrDefault(cp, 0) - 1; if (left < 0) return false; count.put(cp, left); } return count.values().stream().allMatch(v -> v == 0); }}in the room
How to say it in the interview
talk track
- Ask about the alphabet — lowercase only? That decides int[26] vs a HashMap.
- Mention the early length check: it's what makes "no negative count" enough to prove all counts are zero.
traps
- Skipping the length check, then only testing for negatives — "ab" vs "a" would return true.
- Comparing two
Integercounts from maps with==— it compares references and fails above 127. Useequalsorint.
what they ask next
Follow-ups
Find All Anagrams in a String (LC 438)?
Slide a window of length |p| over s, updating the 26 counts as characters enter and leave — see the Sliding Window chapter.
before you submit
Edge cases to test
- Different lengths → false immediately.
- Same letters, different counts ("aacc" vs "ccac") → false.
- One letter each ("a", "a") → true.
practise next
Similar problems
- #49Group AnagramsMediumin Arrays & Strings
- #383Ransom NoteEasyin Hashing
- #567Permutation in StringMediumin Sliding Window