Java - Checking Whether Two Strings are Anagrams

1. Overview

In this tutorial, We'll learn how to check if the two given strings are anagrams or not in java programming language.

Anagram means two string should be same characters but order is not important. So, that means characters can be another order.

Note that character count also should be matched. Suppose if the string1 has 10 chars where as string 2 has 9 characters so these two are not anagams.

Example 1:

String 1: "abaac"

String 2: "caaba"

Output: true

Example 2:

String 1: "listen"

String 2: "silent"

Output: true

Example 3:

String 1: "aap"

String 2: "pap"

Output: false

2. Java - Checking Whether Two Strings are Anagrams Using Sort

First solution is sort the first two string characters and then compare them. If both strings are same then these two strings are anagrams. If the two strings are not same then strings are not anagrams.

Use Arrays.sort() method to sort the string character as char array.

Use String.equals() method to compare the two strings contents.

Look at the below code.

Time complexicity: O(nlogn)

package com.javaprogramto.programs.strings.anagrams;

import java.util.Arrays;

public class CheckStringsAnagramsExample {

	public static void main(String[] args) {

		String str1 = "abaac";
		String str2 = "caaba";

		boolean isAnagram = isStrinsAnagrams(str1, str2);
		System.out.println(isAnagram);

		str1 = "listen";

		str2 = "silent";

		isAnagram = isStrinsAnagrams(str1, str2);
		System.out.println(isAnagram);

		str1 = "aap";

		str2 = "pap";

		isAnagram = isStrinsAnagrams(str1, str2);
		System.out.println(isAnagram);

	}

	private static boolean isStrinsAnagrams(String str1, String str2) {

		// converting str1 to char array
		char[] strCharArray1 = str1.toCharArray();

		// converting str2 to char array
		char[] strCharArray2 = str2.toCharArray();

		// sorting two strings char arrays using Arrays.sort() method
		Arrays.sort(strCharArray1);
		Arrays.sort(strCharArray2);

		// converting char arrays back to strings
		str1 = new String(strCharArray1);
		str2 = new String(strCharArray2);

		// comparing two strings
		if (str1.equals(str2))
			return true;

		return false;
	}

}

Output:

true
true
false

3. Java - Checking Whether Two Strings are Anagrams - Optimized Solution

The above solution takes nlogn logarthemetic execution time. This may not work for the larger input data.

We need to always think before using sorting logic on any problem.

To avoid sorting, we need to think different for better approach.

Here is problem is we need to check each and every character of string 1 is present in the string 2.

Actually, for this problem sorting is not an efficient answer.

We will take one integer array with size of 256. This value is the typical characters are stored in 8 bits so there will be only 256 possible characters.

By default, all values in the int array are initialized with 0.

First, Take the each character from the string and go to the corresponding location in the int array increaemtn by 1 and repeat the same process.

Next, take the each character from second string and go the corresponding location in the same int array, decrement the value 1.

If the one character is present in both strings then first count is increment by 1 and decreemnted by 1. So, count value in the int array becomes 0.

If the one character is present in the first array and the same character element is not present in the second string then the value in the count array will non zero value.

After traversing the two strings, we will check the counts int array values, if any index value is non zero then two strings are not anagrams. 

If all values in the count array is zero then inputs are anagrams.

Look at the below code.

package com.javaprogramto.programs.strings.anagrams;

public class CheckStringsAnagramsExample2 {

	public static void main(String[] args) {

		String str1 = "abaac";
		String str2 = "caaba";

		boolean isAnagram = isStrinsAnagramsOptimized(str1, str2);
		System.out.println(isAnagram);

		str1 = "listen";

		str2 = "silent";

		isAnagram = isStrinsAnagramsOptimized(str1, str2);
		System.out.println(isAnagram);

		str1 = "aap";

		str2 = "pap";

		isAnagram = isStrinsAnagramsOptimized(str1, str2);
		System.out.println(isAnagram);

	}

	private static boolean isStrinsAnagramsOptimized(String str1, String str2) {

		// if two strings lengths are not same then return false
		if (str1.length() != str2.length()) {
			return false;
		}
		int arraySize = 256;

		int[] countsArray = new int[arraySize];

		// increment by 1 from str1, decrement by 1 from str2
		for (int i = 0; i < str1.length(); i++) {
			countsArray[str1.charAt(i)]++;
			countsArray[str2.charAt(i)]--;
		}

		// checking any value is non zero in the counts arrray.
		for (int i = 0; i < countsArray.length; i++) {
			if (countsArray[i] != 0) {
				return false;
			}
		}

		return true;
	}
}

Output:

true
true
false

This code also generates the same output with O(n).

Time complexity: O(n)

Space complexity: O(256)

4. Conclusion

In this tutorial, We've seen how to check if the two strings are Anagrams or not in java.

GitHub

How to sort an array in Java 8 - Arrays.sort()?

How to count substring occurrences in String in Java?