Interview preparation
Valid Anagram
EasyStringsHashingSorting and Searching
1Problem statement
Given two strings s and t of lowercase English letters, return true if t is an anagram of s (same letters with the same counts), otherwise false.
2Examples
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
3Constraints
- 1 ≤ s.length, t.length ≤ 5 × 10⁴
- s and t consist of lowercase English letters.
4Approaches
Approach 1
Brute Force
For every character of s, find and remove one matching character from t.
Time O(n²)Space O(n)
Approach 2
Better: Sort both
Sort both strings and compare.
Time O(n log n)Space O(n)
Approach 3
Optimal: Count letters
Increment counts for s, decrement for t in a 26-slot array; all counts must be zero.
Time O(n)Space O(1) (26 counters)
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const counts = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
counts[s.charCodeAt(i) - 97]++;
counts[t.charCodeAt(i) - 97]--;
}
return counts.every((c) => c === 0);
}
console.log(isAnagram("anagram", "nagaram"));
console.log(isAnagram("rat", "car"));
6Complexity
Time
O(n)
Space
O(1)
7Visual walkthrough
- 1.counts after "rat": r=1, a=1, t=1
- 2.after subtracting "car": c=−1, r=0, a=0, t=1
- 3.non-zero counts → not an anagram