Approach Summary
Count character frequencies in s, decrement for t. If all counts are 0, they are anagrams.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sorting | O(n log n) | O(1) or O(n) depending on language string immutability | Sort both strings alphabetically and test for equality in O(n log n). |
| 2 Approach 2: Character Frequency Array / Map (Optimal) | O(n) | O(1) [at most 26 entries] | Count character occurrences using a 26-element array or hash map in linear time. |
Step 1: Baseline
Approach 1: Sorting
Time: O(n log n)
Space: O(1) or O(n) depending on language string immutability
If two strings are anagrams, their sorted sequences of characters must be identical. Sort both strings and compare them character by character. If equal, return true; otherwise return false.
Approach 1: Sorting Implementation
Approach 1: Sorting
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
Arrays.sort(sArr);
Arrays.sort(tArr);
return Arrays.equals(sArr, tArr);
}
}class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)function isAnagram(s, t) {
if (s.length !== t.length) return false;
return s.split('').sort().join('') === t.split('').sort().join('');
} Step 2: Most Optimized
Approach 2: Character Frequency Array / Map (Optimal)
Time: O(n)
Space: O(1) [at most 26 entries]
Maintain a character frequency map. Increment for each character in s, and decrement for each character in t. If any character in t is missing or its count falls below zero, return false immediately. If the map is empty or all counts are zero at the end, return true.
Approach 2: Character Frequency Array / Map (Optimal) Implementation
Approach 2: Character Frequency Array / Map (Optimal)
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
if (!map.containsKey(t.charAt(i))) return false;
map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
if (map.get(t.charAt(i)) == 0) map.remove(t.charAt(i));
}
return map.isEmpty();
}
}class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
unordered_map<char, int> map;
for (char c : s) map[c]++;
for (char c : t) {
if (map.find(c) == map.end()) return false;
map[c]--;
if (map[c] == 0) map.erase(c);
}
return map.empty();
}
};class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
freq = {}
for c in s:
freq[c] = freq.get(c, 0) + 1
for c in t:
if c not in freq:
return False
freq[c] -= 1
if freq[c] == 0:
del freq[c]
return len(freq) == 0function isAnagram(s, t) {
if (s.length !== t.length) return false;
const map = new Map();
for (const c of s) map.set(c, (map.get(c) || 0) + 1);
for (const c of t) {
if (!map.has(c)) return false;
map.set(c, map.get(c) - 1);
if (map.get(c) === 0) map.delete(c);
}
return map.size === 0;
}Edge Cases to Watch
- Different lengths (e.g. s = "a", t = "ab"; returns false immediately)
- Identical strings (e.g. s = "anagram", t = "anagram"; returns true)
- Single character matching / non-matching
- Non-English / Unicode characters (handled via HashMap instead of fixed 26 array)
Algorithmic Pattern
View Pattern Guide →
Master the Hash Map / Set Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Hash Map / Set pattern.
Framework: Hash Map / Set • Interview Prep: Tested at FAANG •
Explore all Hash Map / Set problems & invariants →
How to Recognize This Pattern
- Check if two strings contain same characters
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
String Hash Map Sorting
Frequently Asked Questions
What is the optimal time and space complexity for Valid Anagram?
The optimal solution for Valid Anagram achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because we perform a single linear scan over s and t. Space complexity is O(1) auxiliary space because the alphabet size is constant (26 lowercase English letters).
How do I identify that Valid Anagram requires the Hash Map / Set pattern?
In technical interviews, look for key problem signals: Check if two strings contain same characters. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Hash Map / Set strategy.
What critical edge cases must be handled in Valid Anagram?
Essential edge cases to verify include: Different lengths (e.g. s = "a", t = "ab"; returns false immediately); Identical strings (e.g. s = "anagram", t = "anagram"; returns true); Single character matching / non-matching; Non-English / Unicode characters (handled via HashMap instead of fixed 26 array). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Valid Anagram?
Valid Anagram is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Apple, Microsoft.