Problem
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
OR
WAP to find out if 2 strings are anagrams or not.
Examples
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 * 10^4sandtconsist of lowercase English letters.
Follow up
What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Sorting the String and Comparing
We perform 2 steps:
- Sort both strings
- Compare the sorted strings
Code
Java
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] ch1 = s.toCharArray();
char[] ch2 = t.toCharArray();
Arrays.sort(ch1);
Arrays.sort(ch2);
return Arrays.equals(ch1, ch2);
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return sorted(s) == sorted(t)
Complexity
- ⏰ Time complexity:
O(n log n)-O(nlogn)for sorting andO(n)for comparison. - 🧺 Space complexity:
O(n)ORO(1)depending on programming language…
Method 2 - Using the Custom Hash Function ❌
The obvious solution is to map each character to a prime number and multiply the prime numbers. So if ‘a’’ -> 2 and ‘b’ -> 3, then
- ‘ab’ ->5
- ‘ba’ ->5
- ‘bab’ ->8
- ‘abba’ ->10
- ‘baba’ ->10
To minimise the chance of overflow, the smallest primes could be assigned to the more frequent letters (e, t, i, a, n). Note: The 26th prime is 101.
In simple terms, write a hash function with as low collision as possible. So 2 strings should generate same hash, if they have same characters.
Gotchas
Caution : But problem with this approach above is hash returning function is not unique. So it may throw out wrong result…so it is highly advisable to have very good hash function.
Code
Java
class Solution {
private static final int[] PRIMES = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101
};
public boolean isAnagram(String s, String t) {
return getHash(s) == getHash(t);
}
private int getHash(String s) {
int hash = 1;
// Convert the string to lowercase to make the function case-insensitive.
s = s.toLowerCase();
for (char ch : s.toCharArray()) {
// Multiply each character's ASCII value representation by its associated prime number.
// A prime number is mapped to each letter: 'a' -> 2, 'b' -> 3, 'c' -> 5, etc.
hash *= PRIMES[ch - 'a'];
}
return hash;
}
}
Complexity
- ⏰ Time complexity:
O(n)- for iterating on string characters. - 🧺 Space complexity:
O(1)
Method 3 - Using 2 Hashmaps
Code
Java
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> freq1 = new HashMap<>();
Map<Character, Integer> freq2 = new HashMap<>();
for (char ch : s.toCharArray()) {
freq1.put(ch, freq1.getOrDefault(ch, 0) + 1);
}
for (char ch : t.toCharArray()) {
freq2.put(ch, freq2.getOrDefault(ch, 0) + 1);
}
return freq1.equals(freq2);
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
freq1: Dict[str, int] = {}
freq2: Dict[str, int] = {}
for ch in s:
freq1[ch] = freq1.get(ch, 0) + 1
for ch in t:
freq2[ch] = freq2.get(ch, 0) + 1
return freq1 == freq2
Method 4 - Counting Characters Using Hashmap
Rather than writing your own hash function, you can use in-built hashmap and then store the first string with count values in that hashmap, and then apply the same logic to do the same, and check if hashmap are same or not. This again takes O(n) time and is better than above approach.
Dry Run
In that case, we should return False, because they are not anagram.
Let’s see one by one.
t = "nagaram"
counter = {"a": 3, "g": 1, "m": 1, "n": 1, "r": 1}
t = "nagaram"
↑
reduce 1 from n
counter = {"a": 3, "g": 1, "m": 1, "n": 0, "r": 1}
t = "nagaram"
↑
reduce 1 from a
counter = {"a": 2, "g": 1, "m": 1, "n": 0, "r": 1}
t = "nagaram"
↑
reduce 1 from g
counter = {"a": 2, "g": 0, "m": 1, "n": 0, "r": 1}
t = "nagaram"
↑
reduce 1 from a
counter = {"a": 1, "g": 0, "m": 1, "n": 0, "r": 1}
t = "nagaram"
↑
reduce 1 from r
counter = {"a": 1, "g": 0, "m": 1, "n": 0, "r": 0}
t = "nagaram"
↑
reduce 1 from a
counter = {"a": 0, "g": 0, "m": 1, "n": 0, "r": 0}
t = "nagaram"
↑
reduce 1 from m
counter = {"a": 0, "g": 0, "m": 0, "n": 0, "r": 0}
Finish. We successfully iterate through all characters in t string. That means two input strings are anagram.
Code
Java
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> freq = new HashMap<>();
for (char ch : s.toCharArray()) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
for (char ch : t.toCharArray()) {
if (!freq.containsKey(ch)) {
return false;
}
freq.put(ch, freq.get(ch) - 1);
if (freq.get(ch) == 0) {
freq.remove(ch);
}
}
return true;
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Check if lengths of s and t are different
if len(s) != len(t):
return False
# Create a frequency dictionary for characters in s
freq: Dict[str, int] = {}
# Increment the counts for characters in s
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
# Decrement the counts for characters in t
for ch in t:
if ch not in freq: # If the character is not in the dictionary, return False
return False
freq[ch] -= 1
if freq[ch] == 0: # Remove the character count if it reaches zero
del freq[ch]
# If all characters match, the strings are anagrams
return True
Complexity
- ⏰ Time complexity:
O(n)- for iterating on string characters. - 🧺 Space complexity:
O(1)- for storing characters in map, it takes O(n) space, but we have only 26 alphabets in string, henceO(26)=O(1)
Method 5 - Counting Characters Using array
As the constraint of the problem is we store only small case letters, so we can use array for that.
We can use ch - 'a' to get the index in array. Why?
We know ascii characters look like:
"a": 97
"b": 98
"c": 99
.
.
.
"y": 121
"z": 122
So, when ch = z, 'z' - 'a' = 122 - 97 = 25.
Code
Java
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a'] += 1;
}
for (int i = 0; i < t.length(); i++) {
if (count[t.charAt(i) - 'a'] == 0) {
return false;
}
count[t.charAt(i) - 'a'] -= 1;
}
return true;
}
}
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Check if string lengths are different
if len(s) != len(t):
return False
# Frequency count array for 26 lowercase English letters
count = [0] * 26
# Increment counts for characters in s
for ch in s:
count[ord(ch) - ord('a')] += 1
# Decrement counts for characters in t
for ch in t:
if count[ord(ch) - ord('a')] == 0: # If count becomes invalid, return False
return False
count[ord(ch) - ord('a')] -= 1
# If all counts are balanced, return True
return True
Complexity
- ⏰ Time complexity:
O(n)- for iterating on string characters. - 🧺 Space complexity:
O(1)(as we store 26 characters)