Valid Anagram LeetCode 242 Deep Dive

LeetCode 242 — Valid Anagram — gives you two strings s and t and asks you to return true if t is an anagram of s, and false otherwise. An anagram is a rearrangement of the characters of one string to form another: t must contain exactly the same characters as s with exactly the same frequencies, just in a potentially different order. For example, s = "anagram" and t = "nagaram" returns true because both contain the characters a(3), n(1), g(1), r(1), m(1). But s = "rat" and t = "car" returns false because the character sets differ.

The problem is rated Easy on LeetCode and is one of the most common introductory string problems. Its real value lies in the discussion it opens: two distinct approaches (sorting vs frequency counting) with different time and space trade-offs, and the Unicode follow-up that forces you to generalize from a fixed-alphabet assumption to an open character set. Together these dimensions make it a richer interview problem than its Easy rating suggests.

The constraints for the standard problem state that s and t consist of lowercase English letters only, which means the alphabet has exactly 26 characters. This constraint is what enables the int[26] array optimization. The follow-up question explicitly relaxes this: what if the input contains Unicode characters? A robust solution must either handle this naturally (HashMap) or be extended to do so.

The simplest approach is to sort both strings and compare the results. If sorted(s) == sorted(t), they are anagrams — the sorted form of any string is a canonical representation of its character multiset, so two strings are anagrams if and only if their sorted forms are identical. For s = "anagram" and t = "nagaram", both sort to "aaagmnr", so the comparison returns true.

The time complexity of the sorting approach is O(n log n) where n is the length of the longer string, dominated by the sort. The space complexity is O(n) for the sorted copies of the strings (Python's sorted() returns a list; Java's Arrays.sort requires converting to a char array). Always add the length check as an early exit: if len(s) != len(t), return false immediately without sorting — if the lengths differ, the strings cannot be anagrams.

The sorting approach is simple and easy to remember, making it useful when you need a quick correct solution. However, it is not optimal. If the interviewer explicitly asks for O(n) time, sorting does not qualify. The sorting approach also makes an implicit assumption: that the characters are sortable in a reasonable way, which is generally true for Unicode but may have nuance with certain normalization forms.

For strings consisting of lowercase English letters, the optimal approach uses an integer array of size 26 — one slot for each letter. Iterate over s and increment count[c - 'a'] for each character c. Then iterate over t and decrement count[c - 'a']. Finally, check that every element of count is zero: if any is non-zero, the frequencies differ and the strings are not anagrams. If all are zero, the strings are anagrams.

An equivalent single-pass formulation is possible: iterate over s and t simultaneously, incrementing for s and decrementing for t, then check all zeros. This is the same algorithm in slightly different form. The key insight is that the count array acts as a difference counter: positive values mean s has more of that character, negative values mean t has more. All zeros means the distributions are identical.

The time complexity is O(n) for iterating over both strings plus O(1) for checking 26 array positions. The space complexity is O(1) — the array is fixed size regardless of input length. This is the optimal solution for the lowercase-only version of the problem and is the approach interviewers most want to see when they ask for O(n) time.

Instead of a fixed-size array, use a HashMap (or Python Counter) to count character frequencies. Build a frequency map for s, then for each character in t, decrement its count in the map (or check if it exists). If any character in t is not in the map or has a zero count, the strings are not anagrams. Alternatively, build two maps and compare them for equality.

The Python Counter makes this trivial: Counter(s) == Counter(t) is the entire solution — Counter is a subclass of dict that counts hashable objects, and two Counters are equal if they have the same keys with the same values. In Java, you build a HashMap<Character, Integer> manually: for each character in s, increment its count; for each character in t, decrement its count; then check that all values are zero or that the map has no non-zero entries.

The HashMap approach has O(n) time complexity and O(k) space complexity where k is the number of distinct characters. For the lowercase-only version, k <= 26, so it is effectively O(1) space — but for the Unicode follow-up, k can be much larger. The HashMap approach scales to any character set without modification, making it the preferred solution when Unicode support is required.

Instead of building two separate frequency maps and comparing them, use a single counter: iterate over s and t simultaneously, incrementing the counter for each character in s and decrementing for each character in t. After processing both strings, check that all counter values are zero. This avoids allocating two maps and the overhead of a map equality check.

The single-counter approach is equivalent to the two-map comparison but more memory-efficient in practice because you maintain one data structure instead of two. It also exits early in spirit: if you check counts after each position, you could detect a discrepancy and exit — though in practice most implementations do a single final pass. The two key properties are: (1) only one counter is created, and (2) the final check for all-zeros is O(k) where k is the number of distinct characters.

This optimization matters most in memory-constrained environments or when the strings are very long with many distinct characters. For the typical competitive programming scenario, the difference is negligible. Its value as an interview talking point is that it shows you think about implementation details beyond just correctness — a sign of engineering maturity.

Python — Counter approach: from collections import Counter; def isAnagram(s, t): return Counter(s) == Counter(t). One line. Python — array approach: 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; return all(x == 0 for x in count). The array approach is O(n) time and O(1) space, optimal for the lowercase version. For Unicode: replace count = [0] * 26 with count = {} and use count.get(c, 0) for lookups.

Java — int[26] approach: public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] count = new int[26]; for (char c : s.toCharArray()) count[c - 'a']++; for (char c : t.toCharArray()) count[c - 'a']--; for (int x : count) if (x != 0) return false; return true; }. The early length check prevents unnecessary work. The final loop over 26 elements is O(1). For the Unicode follow-up, replace int[26] with HashMap<Character, Integer> and update accordingly.

Both Python and Java solutions handle all edge cases: single-character strings, all-same-character strings, and strings with many repeated characters. The length check as a first line is a best practice that applies to both languages and both approaches — it is a constant-time O(1) short-circuit that eliminates all cases where anagram is impossible without any character inspection.

Find All Anagrams in a String (LeetCode 438) extends Valid Anagram to a sliding window context: given strings s and p, find all start indices in s where a substring of length len(p) is an anagram of p. The approach uses the same frequency counting window, sliding it across s and checking validity at each position. This is the direct extension of the Valid Anagram pattern to a larger problem.

Group Anagrams (LeetCode 49) groups a list of strings by their anagram equivalence class. The canonical solution uses a sorted string as the dictionary key (sorting each word and grouping by the sorted form), or uses a tuple of 26 character counts as the key. Both rely on the same anagram-detection logic from LeetCode 242 applied to a collection rather than a pair.

The character counting pattern recurs throughout string algorithms: Longest Common Prefix (LeetCode 14) checks character-by-character alignment; Minimum Window Substring (LeetCode 76) uses two frequency maps and a sliding window to find the smallest substring containing all characters of a target; Ransom Note (LeetCode 383) is nearly identical to Valid Anagram — check if one string's characters can be covered by another's. Mastering the frequency array and HashMap patterns for Valid Anagram directly enables solving this entire family of problems.