Valid Anagram
EasyGiven two strings s
and t,
return true
if t
is an anagram of s,
and false
otherwise.
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Explanation
There are two main approaches to solve this problem: sorting and hash map (frequency counting).
Approach 1: Sorting
The simplest approach is to sort both strings and compare them character by character. If they are anagrams, sorting will arrange both strings in the same order.
Approach 2: Hash Map (Recommended)
A more efficient approach is to count character frequencies using a hash map (or array of size 26 for lowercase English letters):
- If the strings have different lengths, they cannot be anagrams → return
false - Create a frequency array/hash map to count character occurrences in
s - Decrement the count for each character in
t - If all counts are zero, the strings are anagrams → return
true
This approach works because two strings are anagrams if and only if they contain the same characters with the same frequencies.
Idea Map
Check len(s) == len(t)
Create count = [0] * 26
For each char c in s:
count[ord(c) - ord('a')]++
For each char c in t:
count[ord(c) - ord('a')]--
Check if all count[i] == 0
Complexity Analysis
Time Complexity
O(n) - We traverse each string once, where n is the length of the strings.
Space Complexity
O(1) - The frequency array has fixed size of 26 (constant space for lowercase English letters).
Code
def isAnagram(s: str, t: str) -> bool:
Initializes the function `isAnagram` which takes two strings `s` and `t` as input and returns a boolean.
if len(s) != len(t):
Checks if the strings have different lengths - if so, they cannot be anagrams.
return False
Returns False immediately if lengths don't match (early exit optimization).
count = [0] * 26
Creates a fixed-size array of 26 zeros to count character frequencies (one for each lowercase letter).
for c in s:
Loops through each character in the first string `s`.
count[ord(c) - ord('a')] += 1
Increments the count for this character (ord(c) - ord('a') maps 'a' to 0, 'b' to 1, etc.).
for c in t:
Loops through each character in the second string `t`.
count[ord(c) - ord('a')] -= 1
Decrements the count for this character. If strings are anagrams, all counts will be zero.
return all(c == 0 for c in count)
Returns True only if all counts are zero (meaning both strings had identical character frequencies).
public boolean isAnagram(String s, String t) {
Initializes the function `isAnagram` which takes two strings `s` and `t` as input and returns a boolean.
if (s.length() != t.length()) {
Checks if the strings have different lengths - if so, they cannot be anagrams.
return false;
Returns false immediately if lengths don't match (early exit optimization).
}
End of the if statement.
int[] count = new int[26];
Creates a fixed-size array of 26 zeros to count character frequencies (one for each lowercase letter).
for (int i = 0; i < s.length(); i++) {
Loops through each character in the first string `s` using index `i`.
count[s.charAt(i) - 'a']++;
Increments the count for this character (charAt(i) - 'a' maps 'a' to 0, 'b' to 1, etc.).
}
End of the first for loop.
for (int i = 0; i < t.length(); i++) {
Loops through each character in the second string `t` using index `i`.
count[t.charAt(i) - 'a']--;
Decrements the count for this character. If strings are anagrams, all counts will be zero.
}
End of the second for loop.
for (int c : count) {
Loops through the count array to check if all values are zero.
if (c != 0) return false;
If any count is non-zero, strings are not anagrams - return false immediately.
}
End of the verification loop.
return true;
All counts were zero, so strings are anagrams - return true.
}
End of the function.
bool isAnagram(string s, string t) {
Initializes the function `isAnagram` which takes two strings `s` and `t` by value and returns a boolean.
if (s.size() != t.size()) {
Checks if the strings have different lengths - if so, they cannot be anagrams.
return false;
Returns false immediately if lengths don't match (early exit optimization).
}
End of the if statement.
int count[26] = {0};
Creates a fixed-size array of 26 zeros to count character frequencies (one for each lowercase letter).
for (char c : s) {
Loops through each character in the first string `s` using range-based for loop.
count[c - 'a']++;
Increments the count for this character (c - 'a' maps 'a' to 0, 'b' to 1, etc.).
}
End of the first for loop.
for (char c : t) {
Loops through each character in the second string `t` using range-based for loop.
count[c - 'a']--;
Decrements the count for this character. If strings are anagrams, all counts will be zero.
}
End of the second for loop.
for (int c : count) {
Loops through the count array to check if all values are zero.
if (c != 0) return false;
If any count is non-zero, strings are not anagrams - return false immediately.
}
End of the verification loop.
return true;
All counts were zero, so strings are anagrams - return true.
}
End of the function.
Edge Cases & Common Mistakes
Different length strings
Always check if the strings have the same length first. If they don't, they cannot be anagrams and you can return false immediately.
Case sensitivity
The problem assumes lowercase letters. If case matters, convert both strings to the same case before comparing.
Unicode characters
For Unicode strings beyond ASCII, use a HashMap instead of a fixed-size array to handle all possible characters.
Sorting approach alternative
You could also sort both strings (O(n log n)) and compare them directly. This is simpler but slower than the hash map approach.
Related Problems
Understanding Arrays vs Strings
Strings and arrays are closely related data structures. A string is essentially a sequence (array) of characters. Understanding how they work under the hood helps you manipulate them efficiently in algorithms.
Learn more about arrays vs strings →Disclaimer: This problem is for educational purposes. Practice the 'Valid Anagram' problem on LeetCode.