Valid Anagram
You're given two strings s and t made of lowercase English letters. Return true if t is an anagram of s, meaning t uses exactly the same letters as s, each the same number of times, possibly in a different order. Otherwise return false. Strings of different lengths can never be anagrams.
Examples
s = "anagram", t = "nagaram" returns true
Both strings contain three a's and one each of n, g, r and m, just in a different order.
s = "rat", t = "car" returns false
The lengths match, but s has a t where t has a c, so the letter counts differ.
Constraints
- 1 <= s.length, t.length <= 5 * 10^4
- s and t consist of lowercase English letters.
Hints
Order doesn't matter here, only how many times each letter shows up. What could you compare between the two strings?
Count letter frequencies, with a hash map or a fixed array of 26 counters.
Return false if the lengths differ. Increment count[c] for each character of s and decrement it for each character of t. The strings are anagrams if every count ends at zero.
Drill This: Your Approach First
Approach
Two strings are anagrams exactly when every letter appears the same number of times in both. After ruling out different lengths, keep one counter per letter in an array of 26: add 1 for each character of s and subtract 1 for the character at the same position in t. If every counter ends at zero, the letters balance out. The array has a fixed size, so extra space is constant.
Time
O(n)
Space
O(1)
Pitfall
Solutions
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;
}
}class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for cs, ct in zip(s, t):
count[ord(cs) - ord('a')] += 1
count[ord(ct) - ord('a')] -= 1
return all(c == 0 for c in count)