Valid Anagram - Solution & Explanation
Problem Statement
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 * 104sandtconsist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Approach Overview
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 1: Approach 1: Sorting
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.
Complexity
Time Complexity: O(n log n), Space Complexity: O(n) due to sorting overhead.
Approach 2: Approach 2: Frequency Counting
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.
Complexity
Time Complexity: O(n), Space Complexity: O(1) as the count array is fixed in size.
Approach 3: Counting
We first determine whether the length of the two strings is equal. If they are not equal, the characters in the two strings must be different, so return false.
Otherwise, we use a hash table or an array of length 26 to record the number of times each character appears in the string s, and then traverse the other string t. Each time we traverse a character, we subtract the number of times the corresponding character appears in the hash table by one. If the number of times after subtraction is less than 0, the number of times the character appears in the two strings is different, return false. If after traversing the two strings, all the character counts in the hash table are 0, it means that the characters in the two strings appear the same number of times, return true.
The time complexity is O(n), the space complexity is O(C), where n is the length of the string; and C is the size of the character set, which is C=26 in this problem.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
C
Approach 4: Default Approach
Try this approach in the editor →Complexity Comparison
| 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. |
| Counting | — |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Valid Anagram - Leetcode 242 - Python • NeetCode • 892,823 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Valid Anagram easy or hard?
Valid Anagram Python/Java solution
How to solve Valid Anagram in O(n)?
What is the best approach for Valid Anagram?
Is Valid Anagram asked at Google/Amazon/Meta?
What data structure is used in Valid Anagram?
What is the time complexity of Valid Anagram?
Ready to solve this problem?
Practice Valid Anagram with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor