# Check if a string is an anagram

Question: Write a function that checks to see if two Strings are anagrams of each other. Hint: an anagram of a word is one that has the same characters in it, but in a different sequence e.g. "listen" and "silent."

Related Tags:

## Basic checks

Before we talk algorithms, let's do some simple checks. If the lengths of the two Strings are not equal, then the Strings cannot be anagrams. Furthermore, convert input Strings to lowercase, assuming that the interviewer asks that the anagrams are to be case-insensitive.

## 1) Using a HashMap to keep tally

A very basic way of solving the problem is to use a `HashMap`, and map each char to the number of times it appears. Here's the pseudocode for such an approach.

1. For each char `c` in `s1`, map it to the number of times it appears using a HashMap.
2. For each char `c` in `s2`, decrement the number of times in our HashMap.
3. If any char `c` in `s2` does not exist in our HashMap, return `false`, as this means a char from `s2` does not exist in `s1`.
4. Now check each value in our `HashMap` to make sure all numbers are decremented to `0`. If so, return `true`.
``````static boolean isAnagramHashMap(String s1, String s2) {

// Make sure that lengths are equal
if (s1.length() != s2.length()) return false;
// Convert to lowercase
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();

// Maps each character found in s1 to # times appear
HashMap<Character, Integer> charHashMap = new HashMap<>();

// character of interest
Character c;

for (int i = 0; i < s1.length(); i++) {
c = s1.charAt(i);

// If it contains the key already, just increment
if (charHashMap.containsKey(c)) {
charHashMap.put(c, charHashMap.get(c)+1);
} else {
charHashMap.put(c, 1);
}
}

for (int i = 0; i < s2.length(); i++) {
c = s2.charAt(i);

// If key exists, decrement it
if (charHashMap.containsKey(c)) {
charHashMap.put(c, charHashMap.get(c)-1);
// Otherwise char in s2 does not exist in s1, so not anagram.
} else {
return false;
}
}

// Now check that all mapped values are back to zero after decrementing.
for (int i = 0; i < s1.length(); i++) {
c = s1.charAt(i);
if (charHashMap.get(c) != 0) {
return false;
}
}

return true;
}
``````

This approach takes O(3n) time and O(n) auxillary space - not very impressive.

## 2) Remove chars one at a time

A better approach would be to remove each char that exist in `s1` from `s2` one at a time.

1. Select char `c` from `s1`.
2. Find index of `c` in s2.
3. Remove `c` from s2.
4. If `c` does not exist, then return false.
5. Iterate through all chars from `s1`, and if `s2`'s length is `0`, return `true`.
``````static boolean isAnagramRemoving(String s1, String s2) {

// Make sure that lengths are equal
if (s1.length() != s2.length()) return false;
// Convert to lowercase
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();

char currentChar;
int indexOfChar;

// Loop through each char in s1
for (int i = 0; i < s1.length(); i++) {

currentChar = s1.charAt(i);
indexOfChar = s2.indexOf(currentChar);

// If c exists in s2, then remove it from s1
if (indexOfChar != -1) {
s2 = s2.substring(0, indexOfChar) + s2.substring(indexOfChar+1, s2.length());
} else {
// char in s1 does not exist in s2
return false;
}

}

// If no more letters in s2, then we have an anagram
return (s2.length() == 0) ? true : false;

}
``````

This is a pretty elegant solution that takes O(n) time, and O(1) space.

## 3) Sorting and comparing

Lastly, we turn our strings into char arrays, sort, and compare. This is a more straightforward method, but may require you to implement your own sorting algorithm. Also, it's not as fun to code as the first two methods.

``````static boolean isAnagramSorting(String s1, String s2) {

// Make sure that lengths are equal
if (s1.length() != s2.length()) return false;
// Convert to lowercase
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();

char[] char1 = s1.toCharArray();
char[] char2 = s2.toCharArray();

// Your own sorting implementation here
Arrays.sort(char1);
Arrays.sort(char2);

for (int i = 0; i < char1.length; i++) {
if (char2[i] != char2[i]) return false;
}

return true;

}
``````

Came up with a better solution or have a question? Comment below!

Next Challenge: