Valid Anagram
Check whether two strings are anagrams — letter-count comparison.
3 min read
hash-map counting strings
Problem#
Return true iff strings s and t contain the same letters with the same frequencies (i.e., one is an anagram of the other).
Examples#
s = "anagram", t = "nagaram"→true.s = "rat", t = "car"→false.
Constraints#
1 <= s.length, t.length <= 5 * 10^4, lowercase letters.
Hints#
Hint
Count letters of one string up, the other down — if every count returns to zero, they match.
Approach#
Single counter array cnt[26]. Increment for s, decrement for t. After the pass, all entries must be 0. Bail early if lengths differ.
Solution#
class Solution {public: bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; int cnt[26] = {0}; for (int i = 0; i < (int)s.size(); ++i) { ++cnt[s[i] - 'a']; --cnt[t[i] - 'a']; } for (int v : cnt) if (v != 0) return false; return true; }};func isAnagram(s string, t string) bool { if len(s) != len(t) { return false } var cnt [26]int for i := 0; i < len(s); i++ { cnt[s[i]-'a']++ cnt[t[i]-'a']-- } for _, v := range cnt { if v != 0 { return false } } return true}class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False cnt = [0] * 26 for i in range(len(s)): cnt[ord(s[i]) - ord('a')] += 1 cnt[ord(t[i]) - ord('a')] -= 1 return all(v == 0 for v in cnt)function isAnagram(s, t) { if (s.length !== t.length) return false; const cnt = new Array(26).fill(0); const a = 'a'.charCodeAt(0); for (let i = 0; i < s.length; i++) { cnt[s.charCodeAt(i) - a]++; cnt[t.charCodeAt(i) - a]--; } return cnt.every((v) => v === 0);}class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] cnt = new int[26]; for (int i = 0; i < s.length(); i++) { cnt[s.charAt(i) - 'a']++; cnt[t.charAt(i) - 'a']--; } for (int v : cnt) if (v != 0) return false; return true; }}function isAnagram(s: string, t: string): boolean { if (s.length !== t.length) return false; const cnt: number[] = new Array(26).fill(0); const a = 'a'.charCodeAt(0); for (let i = 0; i < s.length; i++) { cnt[s.charCodeAt(i) - a]++; cnt[t.charCodeAt(i) - a]--; } return cnt.every((v) => v === 0);}Editorial#
The increment-then-decrement trick avoids two passes. Length mismatch catches the only case where balanced counts could lie (otherwise impossible — sum is zero iff counts match).
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#