242. Valid Anagram
Model: qwen2.5-coder:14b
Topics: Hash Table,Sort
FAANG asked: 1
Acceptance rate: 58.9%
Problem Breakdown
The problem asks us to determine if one string t is an anagram of another string s. An anagram is defined as a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. The inputs are two strings s and t, and the output should be a boolean value: true if t is an anagram of s, and false otherwise.
Inputs:
- Two strings
sandt.
Outputs:
- A boolean value (
trueorfalse).
Implicit Constraints:
- The strings consist only of lowercase English letters.
- The length of both strings is between 1 and 50,000 characters.
Tricky Edge Cases:
- Strings with different lengths cannot be anagrams.
- Strings with the same characters but different frequencies are not anagrams.
- Empty strings should return
trueif both are empty, orfalseotherwise.
Intuition
A brute-force approach would involve generating all permutations of one string and checking if any permutation matches the other string. However, this approach is computationally expensive with a time complexity of O(n!) due to the factorial number of permutations.
The key insight is that two strings are anagrams if they contain the exact same characters with the same frequencies. This leads us to consider using a hash table (or dictionary) to count the occurrences of each character in both strings and then compare these counts.
Approach
- Check Lengths: If the lengths of
sandtare different, returnfalseimmediately. - Count Characters: Use a hash table (dictionary) to count the frequency of each character in string
s. - Decrement Counts: Iterate through string
t, decrementing the counts for each character in the hash table. - Validate Counts: After processing both strings, check if all counts in the hash table are zero. If they are,
tis an anagram ofs; otherwise, it is not.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the strings. We iterate through each string once to count characters and then validate the counts.
- Space Complexity: O(1) or O(k), where k is the number of unique characters (in this case, 26 for lowercase English letters). The space used by the hash table does not grow with the input size.
Solution
def isAnagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
char_count = {}
# Count characters in s
for char in s:
char_count[char] = char_count.get(char, 0) + 1
# Decrement counts based on t
for char in t:
if char not in char_count or char_count[char] == 0:
return False
char_count[char] -= 1
# Validate all counts are zero
return all(count == 0 for count in char_count.values())
Edge Cases Handled
- Different Lengths: The function immediately returns
falseif the lengths ofsandtdiffer. - Empty Strings: If both strings are empty, they are trivially anagrams, so the function returns
true. - Character Frequency Mismatch: The hash table ensures that character frequencies are correctly matched between the two strings.
The solution is correct, efficient, and clear. It handles all edge cases as described in the problem breakdown.