Write a Java method to check whether two lowercase strings are anagrams.
If the lengths differ the answer is no. Otherwise count each letter of the first string up and each letter of the second down in an int[26], and the strings are anagrams if every count ends at zero. O(n) time, O(1) space.
Explain it simply
Anagrams use exactly the same letters the same number of times, like "listen" and "silent". Sorting both and comparing works, but counting is faster.
Line by line
public static boolean isAnagram(String a, String b) {
if (a.length() != b.length()) return false;
int[] count = new int[26];
for (int i = 0; i < a.length(); i++) {
count[a.charAt(i) - 'a']++; // letter seen in a
count[b.charAt(i) - 'a']--; // letter seen in b
}
for (int c : count) {
if (c != 0) return false; // some letter did not cancel out
}
return true;
}
// isAnagram("listen", "silent") returns true
// isAnagram("rat", "car") returns falsech - 'a' turns 'a' into 0, 'b' into 1 and so on, which gives each letter its own slot.
Complexity
Time O(n), space O(1) because the array always has 26 slots.
What to say in the interview
"I compare lengths first, then use a fixed counting array. The sort approach is O(n log n) and simpler to write. If the input can contain Unicode or uppercase letters, I would use a HashMap of character counts instead, which makes space proportional to the number of distinct characters."
Common mistakes
- Using this array on uppercase or non-English text, which causes an ArrayIndexOutOfBoundsException.