Valid Anagram LeetCode Solution: Frequency Counting Foundation

Valid Anagram (#242) is one of those rare LeetCode problems that looks almost too simple on the surface but teaches a pattern you will use in dozens of harder problems. The task is straightforward: given two strings s and t, determine whether t is an anagram of s. Two strings are anagrams if they contain exactly the same characters with exactly the same frequencies.

This valid anagram leetcode problem is tagged Easy, and most candidates solve it in under ten minutes. But the real value is not in solving it — it is in understanding why the optimal approach works. The character frequency counting technique you learn here is the exact same technique behind Group Anagrams (#49), Permutation in String (#567), Minimum Window Substring (#76), and Find All Anagrams in a String (#438).

If you are just starting your LeetCode journey, this problem is the perfect entry point into hash map thinking. If you are revisiting it before an interview, use it as a warm-up to make sure your frequency counting instincts are sharp.

The problem 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 uses every letter from the original exactly once, rearranged into a different order. "listen" and "silent" are anagrams. "hello" and "world" are not.

The key insight is that two strings are anagrams if and only if they have the same character frequency distribution. You do not need to check every possible rearrangement — you just need to verify that every character appears the same number of times in both strings. This transforms a potentially factorial-complexity problem into something solvable in linear time.

The constraints are generous: both strings consist of lowercase English letters and can be up to 50,000 characters long. This rules out brute-force permutation approaches and points you toward either sorting or counting.

The simplest approach to check anagram equivalence is to sort both strings and compare them. If two strings are anagrams, their sorted versions will be identical. "listen" sorted is "eilnst", and "silent" sorted is also "eilnst". This gives you a clean, readable solution.

In Python, this is literally one line: return sorted(s) == sorted(t). In Java or C++, you would convert to character arrays, sort them, and compare. The sort anagram comparison approach is easy to remember, easy to implement, and easy to verify for correctness.

The trade-off is performance. Sorting takes O(n log n) time, where n is the length of the string. For this problem that is perfectly acceptable — 50,000 * log(50,000) is well within time limits. But in an interview, the interviewer will almost certainly ask if you can do better, which leads to Approach 2.

The optimal leetcode 242 solution uses a hash map (or fixed-size array) to count character frequencies. The idea is simple: iterate through s and increment the count for each character, then iterate through t and decrement the count for each character. If all counts return to zero, the strings are anagrams.

In practice, you can use a single array of size 26 (one slot per lowercase letter) instead of a hash map. Walk through s, incrementing counts. Walk through t, decrementing counts. At the end, check that every count is zero. This valid anagram hash map approach runs in O(n) time with O(1) space — 26 slots is constant regardless of input size.

An alternative implementation uses two separate frequency maps and compares them at the end. This is equally correct but uses twice the space and requires an extra comparison step. The single-map increment-decrement pattern is cleaner and more commonly expected in interviews.

Here is the mental model: imagine 26 buckets labeled a through z. Pour all the letters from s into the buckets, one at a time. Then remove all the letters from t, one at a time. If every bucket is empty at the end, the strings are anagrams. If any bucket has a positive or negative count, they are not.

The sorting approach works, but character frequency counting is the approach you should internalize. It runs in O(n) time versus O(n log n), and more importantly, it extends directly to harder problems. Once you understand how to build and compare frequency maps, you have the toolkit for an entire family of string problems.

Group Anagrams (#49) asks you to group strings that are anagrams of each other. The frequency count becomes the hash key — strings with identical frequency distributions land in the same bucket. Permutation in String (#567) uses a sliding window with a frequency count to check whether any substring of one string is a permutation of another. Find All Anagrams (#438) extends this to find every starting index.

Minimum Window Substring (#76) — one of the hardest sliding window problems — uses the same frequency counting foundation but adds the complexity of tracking when all required characters are satisfied. Every one of these problems starts with the exact technique you learn in Valid Anagram. That is why this Easy problem punches well above its difficulty rating.

Anagram detection through frequency counting also appears in real-world applications: spell checkers, plagiarism detection, and DNA sequence analysis all use variants of this technique.

The most important edge case is different string lengths. If len(s) != len(t), you can immediately return false without doing any counting or sorting. This O(1) early return demonstrates good engineering instincts and saves unnecessary computation. Always check this first.

Empty strings are another consideration. Two empty strings are technically anagrams of each other (both have zero characters), so the correct return value is true. Most implementations handle this correctly by default, but mention it to show thoroughness.

The follow-up question interviewers love: "What if the inputs contain Unicode characters?" With Unicode, you cannot use a fixed-size array of 26. You need a proper hash map that can handle any character. In Python, collections.Counter handles this automatically. In Java, you would use a HashMap<Character, Integer> instead of int[26]. This is a common way interviewers gauge whether you can adapt a solution to changing constraints.

Valid Anagram is not just another Easy problem to check off your list. It is the entry point to frequency counting, one of the most reusable patterns in all of LeetCode. The increment-decrement technique on a fixed array is the same pattern behind dozens of medium and hard problems involving string comparison, sliding windows, and hash map aggregation.

The problem also teaches you to think about trade-offs. Sorting is simpler but slower. Frequency counting is faster but requires more careful implementation. In an interview, showing both approaches and explaining why you prefer the O(n) solution demonstrates the kind of analytical thinking that gets you hired.

If you want to build lasting recall for this pattern, add it to your YeetCode flashcard deck. Spaced repetition ensures you can recall the frequency counting technique instantly when you see it in a harder problem — whether that is Group Anagrams, Permutation in String, or Minimum Window Substring. The pattern is the same; only the wrapper changes.