Watch 10 video solutions for Valid Anagram, a easy level problem involving Hash Table, String, Sorting. This walkthrough by NeetCode has 660,717 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104s and t consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Problem Overview: Given two strings s and t, determine whether t is an anagram of s. Two strings are anagrams if they contain the same characters with the same frequency, just arranged in a different order.
Approach 1: Sorting (O(n log n) time, O(1) or O(n) space)
Sort both strings and compare the results. If two strings are anagrams, their sorted forms must be identical because sorting places identical characters in the same order. The process is simple: convert both strings to arrays, apply a sorting algorithm, and check if the sorted outputs match. Sorting dominates the runtime, giving O(n log n) time complexity. Space complexity depends on the language implementation—some sorting algorithms operate in-place while others allocate extra memory. This approach works well when code clarity matters more than optimal performance and is easy to implement in languages with built-in sort functions.
Approach 2: Frequency Counting (O(n) time, O(1) space)
Count how many times each character appears in both strings and verify that the counts match. Use a fixed-size frequency array or a hash table where the key represents a character and the value represents its frequency. Iterate through string s and increment counts, then iterate through t and decrement them. If any count becomes negative or a character is missing, the strings are not anagrams. Because each character is processed once, the runtime is O(n). Space complexity is O(1) when the character set is fixed (for example, 26 lowercase English letters). This approach leverages concepts from string manipulation and efficient counting techniques often used with hash tables.
The key insight is that anagrams differ only in order, not in character distribution. Frequency counting directly checks this invariant, avoiding the cost of sorting.
Recommended for interviews: The frequency counting approach. Interviewers expect candidates to recognize that sorting is unnecessary and that character counts fully determine whether two strings are anagrams. Showing the sorting approach first demonstrates baseline problem solving. Switching to the O(n) counting solution shows algorithmic optimization and familiarity with hash-based counting patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) to O(n) | Quick implementation using built-in sort when performance is not critical |
| Frequency Counting (Hash Table / Array) | O(n) | O(1) | Optimal solution for interviews and large inputs |