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.
This approach involves sorting both strings and comparing them. If they are anagrams, both sorted strings will be identical since an anagram is defined as a rearrangement of letters. The time complexity mainly depends on the sorting step, which is O(n log n), where n is the length of the strings. Space complexity is O(1) if sorting is done in-place, otherwise O(n) with additional space for sorted copies.
We first check if the lengths of the strings are equal; if not, they cannot be anagrams. We use qsort to sort both strings. Then, we use strcmp to check if the sorted versions are equal. If they are, it means t is an anagram of s.
Time Complexity: O(n log n), Space Complexity: O(n) due to sorting overhead.
This approach uses two arrays (or hashmaps for more general cases) to count the frequency of each character in both strings. Since the problem constraints specify lowercase English letters, array indices (0-25) can be used to count character occurrences.
Iterate over both strings simultaneously, adjusting a count array to track net character frequency. If all counts are zero at the end, t is an anagram of s.
Time Complexity: O(n), Space Complexity: O(1) as the count array is fixed in size.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting | Time Complexity: O(n log n), Space Complexity: O(n) due to sorting overhead. |
| Approach 2: Frequency Counting | Time Complexity: O(n), Space Complexity: O(1) as the count array is fixed in size. |
| 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 |
Valid Anagram - Leetcode 242 - Python • NeetCode • 842,353 views views
Watch 9 more video solutions →Practice Valid Anagram with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor