Problem Overview
Difficulty: Easy
LeetCode Pattern: Arrays & Hashing
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Note: Anagram is a word or phrase formed by rearranging the letters of another word or phrase.
Input:
· s = "anagram"
· t = "nagaram"
Output:
· true
Explanation:
· Both strings contain:
· 'a': 3 times
· 'n': 1 time
· 'g': 1 time
· 'r': 1 time
· 'm': 1 time
· So they are anagrams.
Input:
· s = "ram"
· t = "car"
Output:
· false
Explanation:
· String s contains 'm'.
· But string t does not.
· So they are not anagrams.Step 1: Clarify Requirements
Can the input strings be empty?
Yes. Return true.
Can they contain uppercase characters?
Yes.
Are strings ASCII (128 characters)?
Yes.
Step 2: Discuss Approaches
1/ Sort Strings (Brute Force ⚠️)
Logic:
Sort both the strings
Return true if they are equal
Return false otherwise
Big O:
Time Complexity: O(n·logn)
Space Complexity: O(n)
2/ Use a Map (Optimal ✅)
Logic:
Initialize an empty map
Key will be character
Value will be char frequency
Loop through the first string:
+1 to each char’s count
Loop through the second string:
-1 to each char’s count
At the end, check if any count ≠ 0
Return false → not an anagram
Otherwise, return true
Big O:
Time Complexity: O(n)
Space Complexity: O(1)
Max 128 keys in map (constant)
Step 3: Write Code (Optimal)
Python
Java
C++
Step 4: Answer Follow-Ups
What if you can’t use a map?
Use a fixed-size array for counts.
What if case doesn’t matter?
Convert both strings to lowercase.
Then run our same algorithm.
What if input contains Unicode?
Our logic still works.
But space complexity changes to O(n).