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 frequencies, but possibly in a different order.
Approach 1: Sorting (O(n log n) time, O(1) or O(n) space)
The simplest strategy is to sort both strings and compare the results. If two strings are anagrams, sorting their characters will produce identical sequences. Convert both strings to character arrays, call a sorting routine, and check whether the sorted results match. Sorting dominates the runtime, giving O(n log n) time complexity where n is the string length. Space complexity depends on the language implementation of sorting: some use O(1) extra space while others allocate O(n). This method is easy to implement and reliable, especially when the input size is small. It relies directly on sorting rather than extra data structures.
Approach 2: Frequency Counting (O(n) time, O(1) space)
A more efficient method counts how often each character appears. Iterate through string s and increment counts in a frequency structure such as an array of size 26 (for lowercase letters) or a hash map. Then iterate through t and decrement the counts. If any count becomes negative or the lengths differ, the strings cannot be anagrams. After processing both strings, all counts should be zero if they contain the same characters. This approach runs in linear O(n) time because each string is scanned once. The extra space stays constant O(1) when using a fixed-size array, or O(k) with a hash table where k is the character set size. It works well for large inputs and is the standard optimized solution for this string problem.
Recommended for interviews: Start by mentioning the sorting approach because it clearly shows the anagram property. Then move to frequency counting as the optimized solution. Interviewers typically expect the O(n) counting method because it avoids sorting and demonstrates efficient use of hash tables or fixed-size arrays.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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)–O(n) | Simple implementation when performance is not critical |
| Frequency Counting (Hash Map / Array) | O(n) | O(1) for fixed alphabet | Optimal approach for interviews and large inputs |
Valid Anagram - Leetcode 242 - Python • NeetCode • 660,717 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