How to check if two String are Anagram in Java - Program Example

Write a Java program to check if two String are anagram of each other, is another good coding question asked at fresher level Java Interviews. This question is on similar level of finding middle element of LinkedList in one pass and swapping two numbers without using temp variable. By the way two String are called anagram, if they contains same characters but on different order e.g. army and mary, stop and pots etc. Anagrams are actually mix-up of characters in String. If you are familiar with String API, i.e. java.lang.String than you can easily solve this problem. In order to check if  Strings are anagram, you need to get there character array and see if they are equal or not. Though you can also use indexOf(), substring() and StringBuffer or StringBuilder  class to solve this question. In this Java program, we will see 3 ways to solve this interview questions, and check if two String are anagram or not. By the way, if you are preparing for Java interview, it's good to prepare some data structures and algorithms questions as well. More often, there is one or more questions from programming, coding and logic in these interviews.


Java program to check if String is anagram

String Anagram Check - 3 ways to find if two Strings are anagrams or notAs I said, there are multiple ways to find if two string are anagram or not. Classical way is getting character array of each String, and then comparing them, if both char array is equal then Strings are anagram. But before comparing, make sure that both String are in same case e.g. lowercase or uppercase and character arrays are sorted, because equals method of Arrays, return true, only if array contains same length, and each index has same character. 


For simplicity, I have left checking if String is null or empty and converting them into uppercase or lowercase, you can do that if you want. If Interviewer ask you to write production quality code, then I would suggest definitely put those checks and throw IllegalArgumentException for null String or you can simply return false. I would personally prefer to return false rather than throwing Exception, similar to equals() method. Anyway, here are three ways to check if two String are Anagram or not. I have also included a JUnit Test to verify various String which contains both anagram and not.

import java.util.Arrays;

/**
 * Java program - String Anagram Example.
 * This program checks if two Strings are anagrams or not
 *
 * @author Javin Paul
 */
public class AnagramCheck {
   
    /*
     * One way to find if two Strings are anagram in Java. This method
     * assumes both arguments are not null and in lowercase.
     *
     * @return true, if both String are anagram
     */
    public static boolean isAnagram(String word, String anagram){       
        if(word.length() != anagram.length()){
            return false;
        }
       
        char[] chars = word.toCharArray();
       
        for(char c : chars){
            int index = anagram.indexOf(c);
            if(index != -1){
                anagram = anagram.substring(0,index) + anagram.substring(index +1, anagram.length());
            }else{
                return false;
            }           
        }
       
        return anagram.isEmpty();
    }
   
    /*
     * Another way to check if two Strings are anagram or not in Java
     * This method assumes that both word and anagram are not null and lowercase
     * @return true, if both Strings are anagram.
     */
    public static boolean iAnagram(String word, String anagram){
        char[] charFromWord = word.toCharArray();
        char[] charFromAnagram = anagram.toCharArray();       
        Arrays.sort(charFromWord);
        Arrays.sort(charFromAnagram);
       
        return Arrays.equals(charFromWord, charFromAnagram);
    }
   
   
    public static boolean checkAnagram(String first, String second){
        char[] characters = first.toCharArray();
        StringBuilder sbSecond = new StringBuilder(second);
       
        for(char ch : characters){
            int index = sbSecond.indexOf("" + ch);
            if(index != -1){
                sbSecond.deleteCharAt(index);
            }else{
                return false;
            }
        }
       
        return sbSecond.length()==0 ? true : false;
    }
}

JUnit Test Case for String Anagram Exmaple

here is our JUnit tests for all three 3 methods of AnagramCheck class, we have actually tested all method with similar set of input.
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * JUnit test class to test various anagram program for various String input.
 */
public class StringAnagramTest {
   
 
    @Test
    public void testIsAnagram() {
        assertTrue(AnagramCheck.isAnagram("word", "wrdo"));
        assertTrue(AnagramCheck.isAnagram("mary", "army"));
        assertTrue(AnagramCheck.isAnagram("stop", "tops"));
        assertTrue(AnagramCheck.isAnagram("boat", "btoa"));
        assertFalse(AnagramCheck.isAnagram("pure", "in"));
        assertFalse(AnagramCheck.isAnagram("fill", "fil"));
        assertFalse(AnagramCheck.isAnagram("b", "bbb"));
        assertFalse(AnagramCheck.isAnagram("ccc", "ccccccc"));
        assertTrue(AnagramCheck.isAnagram("a", "a"));
        assertFalse(AnagramCheck.isAnagram("sleep", "slep"));
       
    }
   
    @Test
    public void testIAnagram() {
        assertTrue(AnagramCheck.iAnagram("word", "wrdo"));
        assertTrue(AnagramCheck.iAnagram("boat", "btoa"));
        assertFalse(AnagramCheck.iAnagram("pure", "in"));
        assertFalse(AnagramCheck.iAnagram("fill", "fil"));
        assertTrue(AnagramCheck.iAnagram("a", "a"));
        assertFalse(AnagramCheck.iAnagram("b", "bbb"));
        assertFalse(AnagramCheck.iAnagram("ccc", "ccccccc"));
        assertFalse(AnagramCheck.iAnagram("sleep", "slep"));
       
    }
    
    @Test
    public void testcheckAnagram() {
        assertTrue(AnagramCheck.checkAnagram("word", "wrdo"));       
        assertFalse(AnagramCheck.checkAnagram("b", "bbb"));
        assertFalse(AnagramCheck.checkAnagram("ccc", "ccccccc"));
        assertTrue(AnagramCheck.checkAnagram("a", "a"));
        assertFalse(AnagramCheck.checkAnagram("sleep", "slep"));
        assertTrue(AnagramCheck.checkAnagram("boat", "btoa"));
        assertFalse(AnagramCheck.checkAnagram("pure", "in"));
        assertFalse(AnagramCheck.checkAnagram("fill", "fil"));
       
    }
}

Output
Testsuite: StringAnagramTest
Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 0.094 sec

Our AnagramCheck class contains 3 static methods to verify if Strings are anagram or not. First one, takes character array of first String and loop through it, then finds that character in second String, and deletes it by using substring method. If second String doesn't contains character than method return false immediately. At the end of test if second String is empty than both Strings are anagram because they contains same set of characters. To improve performance, we have checked length at very start of this method, as two String with different length can not be anagram of each other. Third method is exactly same of first one, except, it uses deleteCharAt(int index) method of StringBuilder for deleting characters.

That's all on how to check if two String are anagram of each other. Don't forget to check other popular programming and coding questions from various Java interviews, mentioned below :

Related topics:

22 comments :

SARAL SAXENA said...

Hi Javin...few things that I want to add...Two words are anagrams of each other if they contain the same number of characters and the same characters. You should only need to sort the characters in lexicographic order, and compare if String a is equal to String b at all steps.

Here's a code example. Look into Arrays in the API to understand what's going on here.

public boolean isAnagram(String firstWord, String secondWord) {
char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
Arrays.sort(word1);
Arrays.sort(word2);
return Arrays.equals(word1, word2);
}

Tibor Baranyi said...

return sbSecond.length()==0 ? true : false

I think that the conditional operator is unnecessary. :)

Govind Sharma said...

Here is a simple code

import java.util.*;

class Anagram
{
public static void main(String args[]) throws Exception
{
Boolean FLAG=true;

Scanner sc= new Scanner(System.in);

System.out.println("Enter 1st string");

String s1=sc.nextLine();

System.out.println("Enter 2nd string");

String s2=sc.nextLine();

int i,j;
i=s1.length();
j=s2.length();

if(i==j)
{
for(int k=0;k<i;k++)
{
for(int l=0;l<i;l++)
{
if(s1.charAt(k)==s2.charAt(l))
{
FLAG=true;
break;
}
else
FLAG=false;
}
}
}
else
FLAG=false;
if(FLAG)
System.out.println("Given Strings are anagrams");
else
System.out.println("Given Strings are not anagrams");
}
}

Lal said...

Compare the length of the two strings. Return false if they are not same.
Take an empty integer array of size 256 to hold the frequency of occurrence of characters in the string.
Iterate through the first string and increment the frequency of each character in its corresponding location in the integer array.
In the same time, iterate through the second string and decrement the frequency of the character in its corresponding location in the integer array.
Iterate through the integer array to check whether it has the value 0. If not, return false. Otherwise, return true.

For explanation and code http://www.algoqueue.com/algoqueue/default/view/7077888/check-whether-two-strings-are-anagram

Anonymous said...

Guys do we require to implement such a complex logic for this. I was thinking what if we add the ascii value of all the characters in the 2 stings. If they are same then its an anagram and if not then its not an anagram. What you say?

Anonymous said...

What is the complexity of this solution? i am looking for a method to decide whether two Strings are anagaram or not in linear time O(n), can I use this one?

Anonymous said...

@Anonymous, two strings are anagram if they contain if they contain same characters. If converting characters to their ASCII value and adding them, you may get a situation where two differnet letters sum to the same number e.g. 4 + 2 = 6 or 3 +3 = 6, both String has differnet character but there sum is same, so I don't see that logic working. What is shown in the solution is correct.

Victor Rodriguez said...

I don't think any of these solutions ignore punctuation and whitespace.

public static boolean areAnagrams(String one, String two) {
String oneLower = one.toLowerCase();
String twoLower = two.toLowerCase();

int sumOne = 0;
for (int x = 0; x < oneLower.length(); x++) {
Character c = oneLower.charAt(x);
if (Character.isLetterOrDigit(c)) {
sumOne += c.charValue();
}
}

int sumTwo = 0;
for (int x = 0; x < twoLower.length(); x++) {
Character c = twoLower.charAt(x);
if (Character.isLetterOrDigit(c)) {
sumTwo += c.charValue();
}
}

return sumOne == sumTwo;
}

Anonymous said...

Complexity seems to be pow(n,2) i.e. {n square} right? Considering substring computation takes O(n) and we are doing for each of n characters in the string(Assuming both strings of length n)...Is it not a fair idea to use HashMaps and compute the same in O(n) at the cost of memory? You would need 256 entries at max? Any thoughts?

devesh yadav said...

import java.util.*;
import java.lang.String;
public class anagram
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
String str1=new String();
String str2=new String();
System.out.println("Enter any small string");
str1=sc.next();
System.out.println("Enter other small string");
str2=sc.next();
char arr1[]=str1.toCharArray();
char arr2[]=str2.toCharArray();
int l1=str1.length();
int l2=str2.length();
if(l1==l2)
{
for(int i=0;i<l2;i++)
{
for(int j=0;j<l2;j++)
{
if(arr1[i]==arr2[j]);
{
l1++;
break;
}
}
if(l1!=l2+i+1)
{
System.out.println("Not Anagram");
break;
}
}
if(l1==2*l2)
System.out.println("We got Anagram");
}
else
System.out.print("Not equal length");

}
}

Javin Paul said...

@devash, would be great if you could list out some key details about your solution e.g. time and space complexity, how it is better than original solution? what improvements you have done etc. If you are just attempting to solve this problem in your style, then also those detail will help other's to check your solution.

Anonymous said...

public static void findAnagram(String word){

StringBuffer bword= new StringBuffer(word);
String anagram=bword.reverse().toString();
if(word.equals(anagram){
System.out.println("anagram");

}else
System.out.println("not");
}

public static void main(String[] args) {

findAnagram("madam");
findAnagram("must");
}

Anonymous said...

What is the simplest way to check if two String are pemutations of each other? You cannot use Hashtable, or any other data structure, solve the problem with plain logic and primitive programming construct.

Nitin Vashisth said...

One simple way to solve the problem can be:-

public static void main(String args[]) {
String first = "army";
String second = "Mary";
boolean result = isAnagram(first.toLowerCase().trim() , second.toLowerCase().trim());
System.out.println("Is Anagram = "+result);
}

public static boolean isAnagram(String first, String second) {

if(first.length() != second.length())
return false;

HashSet hs = new HashSet();
for(char ch : first.toCharArray()) {
hs.add(ch);
}
for(char ch : second.toCharArray()) {
/* if char is allowed in hashset then it means two strings do not contains same chars */
if(hs.add(ch))
return false;
}
return true;
}

Anonymous said...

The best way of solving it through collections ...great work Nitin

Anonymous said...

More Easier Code than the above all the code
here it is

class Sorted
{
public static void main(String ar[])
{
String a="maonj";
String c="jonam";
char d[]=c.toCharArray();
char b[]=a.toCharArray();
if(b.length!=d.length)
{
System.out.println("It's not Anagram");
System.exit(0);}
for(int i=0;ib[j])
{
char temp=b[i];
b[i]=b[j];
b[j]=temp;
}
} } System.out.println("first");
for(int k=0;kd[j])
{
char temp=d[i];
d[i]=d[j];
d[j]=temp;
}
} }
System.out.println("Second");
for(int k=0;k<b.length;k++)
{
System.out.println(d[k]);
}

int count=0;

for(int i=0;i<d.length;i++)
{
if(b[i]!=d[i])
{
System.out.println("It's not Anagram");
count=1;
break;

}
}
if(count==0)
{
System.out.println("It's Anagram");
}

}
}

Vijay Raj Reaper said...

Solution given by @Nitin Vashisth fails in repeated letters test case.
Eg: word1 = "abc";
word2 = "bbc";

Because HashSet never keeps the duplicate data.
The Best way to deal with this problem is only by sorting.

Chris S. said...

Seems like there's a way easier way than the problem described here, that would be solved in way less time.

Create an int array 26 long. For each letter in the string (string.charAt(i)) add 1 to the letter corresponding in int array ('e' or 'E' = array[5]).

For string 2, subtract one each time.

It's an anagram if the array is all zeroes at the end.

This is solved in O(n) time and O(1) space. As opposed to sorting them which is O(nLog(n)) at best.

Anonymous said...

s1='abcd'
s2='dabc'

if sorted(s2)==sorted(s1):
print 'anagram'
else:
print 'not anagram'

#less time complexity

def findAnagram(s1,s2):
c1=[0]*26
c2=[0]*26

for i in range(len(s1)):
position=ord(s1[i])-ord('a')
c1[position]+=1
for i in range(len(s2)):
position=ord(s2[i])-ord('a')
c2[position]+=1
if c1==c2:
print 'anagrams'
else:
print 'not anagrams'

findAnagram("abcdx","dabcx");

MyserY said...

I do this in O(n) and space O(1), the trick is use xor gates.
public static boolean isAnagram(String word, String anagram){
if (word.length() != anagram.length())
return false;

int xorGate = 0; //Xor gate is special for check ocurrences A^B^A == B also A^A == 0
for (int i = 0; i < word.length(); i++) {
xorGate ^= word.charAt(i)^anagram.charAt(i);
}
return xorGate == 0;
}

Cherss

MyserY said...

i have a bug in my last post, i fixx it whit 2 xor and some logics.
public static boolean isAnagram(String word, String anagram)
{
if (word.length() != anagram.length())
return false;
int xorGateW = 0; //Xor gate is special for check ocurrences A^B^A == B also A^A == 0
int xorGateA = 0; //Xor gate is special for check ocurrences A^B^A == B also A^A == 0
for (int i = 0; i < word.length(); i++) {
xorGateW ^= word.charAt(i);
xorGateA ^= anagram.charAt(i);
}
if (xorGateW != 0 || xorGateA != 0)
return (xorGateW^xorGateA) == 0;
else
return (xorGateW != 0 && xorGateA == 0) ||
(xorGateW == 0 && xorGateA != 0);
}
whit this test like assertFalse(StringAnagram.isAnagram("ffff", "aaaa")) will pass.

MyserY said...

i get other solution similar to mapreduce solutions ...
public static boolean anAnagram(String word, String anagram)
{
if (word.length() != anagram.length())
return false;
Map mapW = new HashMap<>();
Map mapA = new HashMap<>();
for (int i = 0; i < word.length(); i++) {
incrementMap(mapW, word.charAt(i));
incrementMap(mapA, anagram.charAt(i));
}
return mapW.entrySet().equals(mapA.entrySet());
}

private static void incrementMap(Map map, Character c) {
if (map.containsKey(c))
map.put(c, map.get(c)+1);
else
map.put(c, 1);
}

Post a Comment