Valid Anagram
Difficulty: Medium
Asked in: Google, Amazon, Microsoft
Understanding The Problem
Problem Description
Given two strings
s
and
t
, Write a program to check whether the two strings are an
anagram
of each other or not.
Problem Note:
-
s
is an anagram oft
if the characters ofs
can be rearranged to formt
. - You may assume the string contains only lowercase alphabets.
Example 1
Input: s = “afteracademy” , t = “academyafter”
Output: 1
Example 2
Input: s = “mindorks”, t = “mindrocks”
Output: 0
Solutions
We will be discussing two solutions for this interview problem
- Using Sorting Technique : Sort the characters in both of the strings and compare them one by one.
- Using Hashing : Create a hashmap of the number of occurrences of each character in the first string and match the second string with it.
You may try this problem here
1. Using Sorting Technique
If you rearrange the letters of
into
s
,
then that would be anagram to each other. If we could sort both the strings, we will have the characters organized in an order which will be identical if both the strings are anagram to each other. So, strings with different lengths would never be an anagram.
t
Solution steps
-
If the length of both the strings are different, then return
0,
else step 2 -
Sort both the strings
s
t
- Compare their characters one by one
-
If any of the character mismatches, return
0
-
If all the characters are identical in both the strings, return
1
Pseudo Code
bool isAnagram(String s, String t) {
if (not s.length() == t.length()) {
return 0
}
char[] str1 = s.toCharArray()
char[] str2 = t.toCharArray()
sort(str1)
sort(str2)
for(i = 0 to i < s.length()){
if(str1[i] != str2[i]){
return 0
}
}
return 1
}
Complexity Analysis
Time Complexity: O(n log n)
Space Complexity: O(n)
Note: In most of the programming language, strings are immutable and thus requires conversion into character array to manipulate it.
Critical Ideas to Think
- What is an anagram?
- Why did sorting work?
- Do you feel that we sorted just because we can match the number of occurrences of each character? If yes, then can you optimize the time complexity?
2. Using Hashing
When we sorted the strings and started matching in the previous approach, we were only checking their occurrences of each character by grouping them together.
So, we could do that by storing the number of occurrences of each character in an array where each index represents the ASCII of the respective character. In this way, we don’t have to reorder the strings, we could directly increment the value at the index by one on each occurrence and compare the second string with it. Instead of using an array whose each index represent the ASCII of character, we could also use a hashmap, whose key is the character itself and the value is their number of occurrence in the first string which works exactly the same as of array.
Solution Steps
-
Return
0
-
Create a
counter
0
-
For each character of
s
increment thecounter[i] (where i is the ASCII of the character)
t
counter[i]
-
If all the index of
counter
0
1
0
Pseudo Code
bool isAnagram(String s, String t) {
if (not s.length() == t.length()) {
return 0
}
// assuming the characters of the strings be lower case only
int counter[26]
for (int i = 0 to i < s.length()) {
counter[s[i] - 97] = counter[s[i] - 97] + 1
counter[t[i] - 97] = counter[t[i] - 97] - 1
}
for (i=0 to i < s.length()) {
if (counter[i] != 0) {
return 0
}
}
return 1
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1), The space utilized by the counter array is constant.
Critical Ideas to Think
-
Why did we return
false
whenevercounter[i] != 0
true
-
Why did we subtract
s[i]
97
- How is this approach better than the sorting approach?
- What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Comparison of Solutions
Suggested Problems to Solve
- Group Anagrams
- Palindrome Permutation
- Find All Anagrams in a String
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!