Valid Anagram — Frequency Array vs HashMap [Amazon, Google Easy]
Sanjeev SharmaAdvertisement
Problem Statement
Input: s = 'anagram', t = 'nagaram' → true. Input: s = 'rat', t = 'car' → false.
Key Insight: Two strings are anagrams iff they have identical character frequency distributions. For lowercase letters only, a 26-element array suffices. Increment for each char in s, decrement for each in t.
C Solution
#include <string.h>
#include <stdbool.h>
bool isAnagram(char* s, char* t) {
if (strlen(s) != strlen(t)) return false;
int cnt[26] = {0};
for (int i = 0; s[i]; i++) cnt[s[i]-'a']++;
for (int i = 0; t[i]; i++) { if (--cnt[t[i]-'a'] < 0) return false; }
return true;
}
C++ Solution
#include <string>
#include <array>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
array<int,26> cnt{};
for (char c : s) cnt[c-'a']++;
for (char c : t) { if (--cnt[c-'a'] < 0) return false; }
return true;
}
};
Java Solution
import java.util.*;
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] cnt = new int[26];
for (char c : s.toCharArray()) cnt[c-'a']++;
for (char c : t.toCharArray()) { if (--cnt[c-'a'] < 0) return false; }
return true;
}
}
JavaScript Solution
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const cnt = new Array(26).fill(0);
for (const c of s) cnt[c.charCodeAt(0) - 97]++;
for (const c of t) { if (--cnt[c.charCodeAt(0) - 97] < 0) return false; }
return true;
}
Python Solution
def isAnagram(s, t):
if len(s) != len(t): return False
count = [0] * 26
for c in s: count[ord(c) - ord('a')] += 1
for c in t:
count[ord(c) - ord('a')] -= 1
if count[ord(c) - ord('a')] < 0: return False
return True
Complexity Analysis
| O(n) time | O(1) space (fixed 26 chars) |
Follow-up (Unicode): Use HashMap<Character,Integer> for arbitrary character sets. Group Anagrams (Problem 32): use sorted string as HashMap key.
Advertisement
