Valid Anagram

Valid Anagram

What is this problem about?

The Valid Anagram interview question is one of the most fundamental string problems. Given two strings, s and t, you need to determine if t is an anagram of s. An anagram is formed by rearranging the letters of one string to form another, using all the original letters exactly once.

Why is this asked in interviews?

This is a universal Hash Table and Sorting coding problem, asked by virtually every tech company, including Apple, Goldman Sachs, and Amazon. It is used as a "smoke test" to ensure a candidate understands the basics of character frequency and time complexity. It allows for a discussion on $O(n \log n)$ vs. $O(n)$ solutions.

Algorithmic pattern used

There are two main Hash Table, Sorting, String interview patterns.

1. Sorting: Sort both strings. If they are identical after sorting, they are anagrams. Time: $O(n \log n)$.
2. Frequency Counting: Use a Hash Map or an array of size 26 (for English letters) to count the occurrences of each character in s. Then, iterate through t and decrement the counts. If all counts are zero at the end, the strings are anagrams. Time: $O(n)$.

Example explanation

Strings: s = "anagram", t = "nagaram"

1. Count in s: {a:3, n:1, g:1, r:1, m:1}
2. Decrement using t:
   • 'n': {a:3, n:0, g:1, r:1, m:1}
   • 'a': {a:2, n:0, g:1, r:1, m:1}
   • 'g': {a:2, n:0, g:0, r:1, m:1} ... and so on.
3. All counts reach zero. Result: true.

Common mistakes candidates make

The most common mistake is not checking if the strings have the same length at the very beginning. If the lengths differ, they cannot be anagrams. Another mistake is assuming the input is only lowercase English letters without clarifying; if Unicode characters are involved, a Hash Map must be used instead of a size-26 array.

Interview preparation tip

When asked a simple question, always discuss the trade-offs. The Sorting approach is easier to write and uses less space in some languages, but the Hash Table approach is faster for very long strings. Showing this level of architectural thinking is what separates good candidates from great ones.