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 * 104sandtconsist of lowercase English letters.
Follow up
What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Solution
Method 1 - Sorting the String and Comparing
We perform 2 steps:
- Sort both strings
- Compare the sorted strings
Code
Java
import java.util.Arrays;
public boolean isAnagram(String s, String t) {
char[] ch1 = s.toCharArray();
char[] ch2 = t.toCharArray();
Arrays.sort(ch1);
Arrays.sort(ch2);
return Arrays.equals(ch1, ch2);
}
Complexity
- ⏰ Time complexity:
O(n log n)-O(nlogn)for sorting andO(n)for comparison. - 🧺 Space complexity:
O(1)
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 - 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> counter = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
counter.put(ch, counter.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
if (!counter.containsKey(ch) || counter.get(ch) == 0) {
return false;
}
counter.put(ch, counter.get(ch) - 1);
}
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 4 - Using 2 Hashmaps
boolean areAnagrams(String s1, String s2) {
if(s1.length() != s2.length()) {
return false;
}
Map <Character, Integer> map1 = new HashMap <>();
Map <Character, Integer> map2 = new HashMap <>();
//process first string
for (char c: s1.toCharArray()) {
map1.put(c, map.getOrDefault(c, 0)+1);
}
//process 2nd string
for (char c: s2.toCharArray()) {
map2.put(c, map.getOrDefault(c, 0)+1);
}
for(char c: map1){
if(map1.get(c) != map2.getOrDefault(c, 0)){
return false;
}
}
return true;
}
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.
Algorithm
- Calculate the count array for string
s
Dry Run
Complexity
- ⏰ Time complexity:
O(n)- for iterating on string characters. - 🧺 Space complexity:
O(1)(as we store 26 characters)
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;
}
}