Valid Anagram
(#242), Easy
Category: String, Hash Table, Sorting
Problem Statement
Given 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, using all the original letters exactly once.
Examples
Input: s = "anagram", t = "nagaram"
Output: true
Explanation: All characters in both strings match in frequency.
Input: s = "rat", t = "car"
Output: false
Explanation: Characters do not match; 'a' and 'r' are not in the same frequency.
Input: s = "aacc", t = "ccac"
Output: false
Explanation: 'a' occurs twice in `s` but only once in `t`, so not an anagram.
Approach
Approach 1: Sorting-Based Comparison
- Check if the lengths of `s` and `t` are equal. If not, return `false`.
- Sort both strings alphabetically.
- Compare the sorted strings. If they match, return `true`; otherwise, return `false`.
// 🔹 Approach: Sorting
var isAnagram = function (s, t) {
if (s.length !== t.length) return false;
return s.split("").sort().join("") === t.split("").sort().join("");
};Approach 2: Two Hash Maps
- Check if the lengths of `s` and `t` are equal. If not, return `false`.
- Create two hash maps to count the frequency of characters in `s` and `t`.
- Iterate through each string and populate the maps.
- Compare the frequency of each character in both maps. If all match, return `true`.
// 🔹 Approach: Two Hash Maps
var isAnagram = function (s, t) {
if (s.length !== t.length) return false;
let sMap = new Map();
let tMap = new Map();
for (let char of s) {
sMap.set(char, (sMap.get(char) || 0) + 1);
}
for (let char of t) {
tMap.set(char, (tMap.get(char) || 0) + 1);
}
for (let [key, val] of sMap) {
if (tMap.get(key) !== val) return false;
}
return true;
};Approach 3: Optimized One Hash Map
- Check if the lengths of `s` and `t` are equal. If not, return `false`.
- Create a hash map to count the characters in `s`.
- Iterate through string `t` and decrement the character count in the map.
- If a character is not found or goes below 0, return `false`.
- If all counts are valid, return `true`.
// 🔹 Approach: One Hash Map (Optimized)
var isAnagram = function (s, t) {
if (s.length !== t.length) return false;
const map = new Map();
for (let char of s) {
map.set(char, (map.get(char) || 0) + 1);
}
for (let char of t) {
if (!map.has(char)) return false;
map.set(char, map.get(char) - 1);
if (map.get(char) < 0) return false;
}
return true;
};Complexity
Time: O(n) – linear time with optimized hash map
Space: O(1) – constant space if input is limited to lowercase letters