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?
The goal of #242 Valid Anagram is to determine whether two strings contain exactly the same characters with the same frequencies, but possibly in a different order. This means both strings must have identical character counts.
A common approach is sorting. If you sort both strings and compare them, anagrams will produce identical sorted sequences. For example, "anagram" and "nagaram" both become the same sorted string. This method is simple and works well for short inputs.
A more efficient technique uses a hash table (frequency map). Count the occurrences of each character in the first string and subtract counts while scanning the second string. If all counts return to zero, the strings are anagrams. This avoids sorting and works in linear time.
While the sorting method is straightforward, the hash table approach is typically preferred in interviews because it achieves O(n) time complexity with minimal extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting Both Strings | O(n log n) | O(1) or O(n) depending on sorting implementation |
| Hash Table / Character Frequency Count | O(n) | O(1) for fixed alphabet (e.g., lowercase letters) |
NeetCode
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.
Time Complexity: O(n log n), Space Complexity: O(n) due to sorting overhead.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5int compare(const void* a, const
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.
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.
Time Complexity: O(n), Space Complexity: O(1) as the count array is fixed in size.
1function
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Valid Anagram is a common beginner-level question asked in technical interviews, including FAANG-style screenings. It tests understanding of hash tables, strings, and time complexity optimization. Interviewers may also ask follow-up variations such as handling Unicode characters.
Yes, you can solve it without sorting by counting character frequencies. By comparing counts between the two strings using a hash map or array, you can determine if both contain identical characters. This approach improves the time complexity to O(n).
The optimal approach uses a hash table or frequency array to count characters in both strings. By incrementing counts for one string and decrementing for the other, you can verify if all counts return to zero. This method runs in O(n) time and is commonly expected in coding interviews.
A hash table or a fixed-size frequency array works best for this problem. Since the characters are usually lowercase English letters, an array of size 26 can efficiently track character counts. This keeps the solution fast and space-efficient.
Leveraging JavaScript arrays for provisional frequency analysis, the resolution calculates balance by comparing all elements for zero values. Such uniformity in zeros confirms anagrams.