Anagram problems are frequently asked in coding interviews. A common challenge is determining whether two strings are anagrams of each other. This problem tests your ability to efficiently manipulate and compare strings.
In this article, we will break down the problem, explain the approach, walk through the JavaScript solution, and provide some notes to enhance your understanding.
Two strings s and t are anagrams if the characters in s can be rearranged to form t. In other words, both strings must contain exactly the same characters with the same frequencies.
Both strings must have the same length.
Both strings must contain the exact same characters, including frequencies.
In simple terms, it’s a frequency matching problem.
isAnagram("anagram", "nagaram"); // true
isAnagram("rat", "car"); // false
isAnagram("listen", "silent"); // true
isAnagram("hello", "world"); // false
To determine if two strings are anagrams, we need to check that both strings have the same characters with the same frequencies.
The strings must have the same length; otherwise, they can’t be anagrams.
We need to check that each character in s appears the same number of times in t.
The most efficient solution in terms of time complexity is using a frequency count with a fixed-size array for storing character counts. This approach runs in O(n) time and O(1) space, making it the fastest for large strings.
/**
* Determines if two strings are anagrams.
* @param {string} s - First string
* @param {string} t - Second string
* @return {boolean}
*/
var isAnagram = function(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0); // Count array for 'a' to 'z'
// Count the frequency of each character
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
count[t.charCodeAt(i) - 'a'.charCodeAt(0)]--;
}
// Check if all counts are 0 (all frequencies match)
return count.every(c => c === 0);
};
Step 1: Initialize a count array to track the frequency of each character (‘a’ to ‘z’).
Step 2: For each character in both strings, increment the count for s and decrement the count for t.
Step 3: If all counts are 0, the strings are anagrams.
Time Complexity: O(n), where n is the length of the string. We traverse the strings once, and the operations inside the loop are constant time.
Space Complexity: O(1), since the count array has a fixed size (26) for the alphabet.
Another efficient solution is to use a hash map to count the frequency of characters in both strings. It runs in O(n) time, but it uses O(n) space due to the hash map storage.
/**
* Determines if two strings are anagrams.
* @param {string} s - First string
* @param {string} t - Second string
* @return {boolean}
*/
var isAnagram = function(s, t) {
if (s.length !== t.length) return false;
const map = {};
// Count characters in s
for (let char of s) {
map[char] = (map[char] || 0) + 1;
}
// Decrease the count for characters in t
for (let char of t) {
if (!map[char]) return false;
map[char] -= 1;
}
return true;
};
Step 1: Check if the lengths of s and t are the same. If not, return false.
Step 2: Create a hash map to count characters in s.
Step 3: Traverse t and decrease the corresponding counts in the map.
Step 4: If any character in t does not exist or has a count of zero in the map, return false.
Step 5: If all counts are correctly decremented, return true.
Time Complexity: O(n), where n is the length of the string. We traverse both strings once and perform constant-time operations on the hash map.
Space Complexity: O(n), where n is the length of the string. The hash map stores the character counts.
While sorting is a simple and elegant solution, it is less efficient than the previous two approaches due to its O(n log n) time complexity. Sorting both strings and comparing them works, but it can be slower for larger inputs.
/**
* Determines if two strings are anagrams.
* @param {string} s - First string
* @param {string} t - Second string
* @return {boolean}
*/
var isAnagram = function(s, t) {
if (s.length !== t.length) return false;
// Sort both strings and compare
return s.split('').sort().join('') === t.split('').sort().join('');
};
Step 1: Check if the lengths of s and t are the same. If they aren’t, return false.
Step 2: Convert both strings to arrays of characters, sort them, and then join them back into strings.
Step 3: If the sorted strings are equal, return true; otherwise, return false.
Time Complexity: O(n log n), where n is the length of the string. Sorting the strings takes O(n log n).
Space Complexity: O(n), for the arrays created while sorting.
✅ Sorting vs Frequency Count: Sorting has a time complexity of O(n log n), which may be less efficient for large strings. The frequency count approach runs in O(n), which is faster for larger inputs.
❌ Case Sensitivity: The problem assumes case sensitivity. For example, "abc" and "ABC" would not be anagrams.
✅ Handling Non-Alphabetic Characters: If needed, the algorithm can be adapted to handle strings with special characters or spaces by normalizing the input.
✅ JavaScript Objects vs Arrays for Counting: When counting characters, arrays are more efficient than objects in this case, but both work fine.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Frequency Count (Array) | O(n) | O(1) |
| Hash Map Approach | O(n) | O(n) |
| Sorting | O(n log n) | O(n) |