242. Valid Anagram - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Examples

Example 1:

Input:

s = "anagram", t = "nagaram"

Output:

true

Explanation:
The letters in "anagram" can be rearranged to form "nagaram", so they are anagrams.

Example 2:

Input:

s = "rat", t = "car"

Output:

false

Explanation:
The letters in "rat" cannot be rearranged to form "car", so they are not anagrams.

Example 3:

Input:

s = "aacc", t = "ccac"

Output:

false

Explanation:
Both words have the same set of characters, but their counts do not match (two "a"s in s vs. one "a" in t).

Constraints:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters.

Follow-up:

What if the inputs contain Unicode characters? How would you adapt your solution?

Hints to Guide the Thought Process

  1. Sorting Approach:

    • If two words are anagrams, they contain the same letters in the same frequency.
    • Sorting the strings will put identical letters in the same order.
    • If the sorted versions of both strings are equal, they are anagrams.
  2. Frequency Count Approach (HashMap or Array):

    • Instead of sorting, we can count the occurrences of each letter in both strings.
    • If the letter frequencies match, the strings are anagrams.
  3. Optimized One-Pass Counting:

    • Since the strings consist only of lowercase English letters (a-z), we can use a fixed-size array of length 26 instead of a hash map for counting.
  4. Handling Unicode Characters (Follow-up Question):

    • If the input contains Unicode characters (not just a-z), we should use a hash map (dictionary in Python, HashMap in Java) instead of an array.

Approach 1: Sorting the Strings

Idea:

  • Sort both s and t and compare them.
  • If they are anagrams, sorting them will result in the same string.

Steps:

  1. Convert both s and t into lists of characters.
  2. Sort both lists.
  3. Compare if they are identical.

Time and Space Complexity:

  • Sorting takes O(n log n) time.
  • Storing sorted strings requires O(n) space.

Python Code:

Python3
Python3

. . . .

Java Code:

Java
Java

. . . .

Why this works:

Sorting arranges the letters in order. If two strings contain the same characters in the same frequency, their sorted versions will be identical.

Drawbacks:

  • Sorting takes O(n log n) time, which is slower than O(n) frequency-based approaches.
  • Extra space is needed to store sorted versions.

Approach 2: Using Hash Map (Frequency Counting)

Idea:

  • Count the occurrences of each letter in s and t using a hash map (dictionary).
  • If both maps are identical, t is an anagram of s.

Steps:

  1. Check if the lengths of s and t are different. If so, return false.
  2. Create a frequency dictionary for s and another for t.
  3. Compare the frequency dictionaries.

Time and Space Complexity:

  • O(n) time: We traverse s and t once.
  • O(n) space: We store the character counts.

Python Code:

Python3
Python3

. . . .

Java Code:

Java
Java

. . . .

Why this works:

  • We count characters efficiently in O(n) time.
  • Using a hash map makes it flexible for Unicode characters.

Drawbacks:

  • Uses extra space for the hash map (O(n) space).

Approach 3: Using an Array (Optimized Counting)

Idea:

  • Since s and t contain only lowercase English letters (a-z), we can use an array of size 26 instead of a hash map.

Steps:

  1. Check if s and t have different lengths. If so, return false.
  2. Create an array count[26] initialized to zero.
  3. Increment values for characters in s, decrement for t.
  4. If the final count array contains only zeros, t is an anagram of s.

Time and Space Complexity:

  • O(n) time: We traverse s and t once.
  • O(1) space: The array size is fixed (26).

Python Code:

Python3
Python3

. . . .

Java Code:

Java
Java

. . . .

Why this works:

  • Uses a fixed size O(1) array instead of a hash map.
  • Efficient O(n) time complexity.

Drawbacks:

  • Limited to lowercase English letters (a-z).

Summary of Approaches

ApproachTime ComplexitySpace ComplexityNotes
Sorting (sorted() or Arrays.sort())O(n log n)O(n)Simple, but not the fastest
Hash Map (Counter() or HashMap)O(n)O(n)Works for Unicode characters
Fixed-Size Array (count[26])O(n)O(1)Fastest for a-z letters

Edge Cases to Consider

  1. Different lengths (len(s) != len(t)) → Return false immediately.
  2. Same characters but different counts (s = "aacc", t = "ccac") → Not an anagram.
  3. Empty strings (s = "", t = "") → Should return true.
  4. Large inputs (s and t close to 5 * 10^4 length) → Use the O(n) methods (hash map or array) instead of sorting.

Follow-up: Unicode Support

  • The array solution (count[26]) does NOT work for Unicode characters.
  • Use a HashMap<Character, Integer> (Java) or Counter() (Python) to support Unicode.

Best Approach

  • For English lowercase letters (a-z): Use the array approach (O(n), O(1) space).
  • For general Unicode text: Use the hash map approach (O(n), O(n) space).

Relevant Problems

  1. Group Anagrams
  2. Find All Anagrams in a String
  3. Longest Palindrome by Rearranging Letters
  4. Check if Two Strings Are Close
  5. Ransom Note
  6. Minimum Steps to Make Two Strings Anagram
  7. Isomorphic Strings
TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
How to guess answers in aptitude test?
How do you implement data partitioning in microservices?
What is Dell famous for?
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.