#242
Valid Anagram
Easy Frequency count
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether t is a rearrangement of s.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: same letters, same counts?
Why this works: one count array: +1 for s, -1 for t. Anagrams leave all zeros.
Example: "anagram" vs "nagaram"
a: 3-3, n: 1-1, g: 1-1, r: 1-1, m: 1-1 → all 0 → true✦Hints open one at a time
Anagrams have the same length and the same count of every letter.
One int[26]: add for s, subtract for t.
↗Approach
If lengths differ return false. Count up for s and down for t; every count must end at 0.
</>Solution (Java)
class Solution {
public 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 c : count) if (c != 0) return false;
return true;
}
}!Common mistake
Sorting both strings — works, but O(n log n) instead of O(n).
Complexity
- Time: O(n).
- Space: O(26).
Topic: Strings
🎬 Episodes 16–20: video coming soon