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: Integer Right Triangles