Category Archives: Anagrams

Checking if any anagram of a given string is palindrome or not

Given a string, how do we check if any anagram of it can be a palindrome?
For example let us consider the string “AAC”. An anagram of it is “ACA” which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.
We can immediately think of a solution where we can generate all anagrams of the given string and check if there is any palindrome exists. But this approach is very lengthy and has exponential time complexity (O(n!)).
The key to solve this problem efficiently is to understand how a palindrome is formed. We all know that a palindrome reads the same when you read from left to right or right to left. 

A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.

So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.

Hence if we check if there is at most one character with odd occurrences in the string we can say that we can form a palindrome from any anagram.

Here is the Java code which implements this algorithm. For simplicity, I assumed that the input string contains only lowercase English alphabets.

How to check if two strings are anagrams of each other

Anagram of a word is nothing but rearrangement of it’s letters to form another word.

For example ‘listen’ is an anagram of ‘silent’ and ‘enlist’.

We have to write a function to check if two given strings are anagrams are not.

We can solve this problem in two different ways. The first way is to sort the two strings and compare them. If they are equal, they are anagrams; otherwise they are not. The intuition behind this is by sorting the letters in the string, it forms a unique pattern. All anagrams must transform to this unique pattern when they are sorted.


For example when we sort the letters in the string ‘listen’ or ‘silent’ it becomes
‘eilnst’ 

Here is the Java function which implements the first method. Here I have used separate strings to hold the sorted sequence so that the original strings are not modified. If the original strings can be modified, we can avoid using the extra String variables.

 public static boolean areAnagrams(String strFirst, String strSecond )
{
char [] charArray = strFirst.toCharArray();
Arrays.sort(charArray);
String strFirstSort = new String( charArray );
charArray = strSecond.toCharArray();
Arrays.sort(charArray);
String strSecondSort = new String( charArray );

return strFirstSort.equals(strSecondSort);
}


Method#2:
The second method is to count the letters in both the strings and match the counts. If the letter count of both the strings is same, then we can conclude that they are anagrams.

In the following Java implementation we do not count the frequencies of letters in both the strings, but we calculate the counts for just one string.

public static boolean areAnagrams(String strFirst, String strSecond )
{
//Assume ASCII charset of size 256 alphabets
int[] charCount = new int[256];

getCharCount(strFirst,charCount);

for( int i = 0; i < strSecond.length(); i++ )
{
char ch = strSecond.charAt(i);
// If count of ch is more in second string, return false
if( charCount[ch] <= 0 )
return false;
else
charCount[ch]--;
}

for( int i = 0; i < 256; i++ )
{
if( charCount[i] > 0 )
return false;
}
return true;
}
public static void getCharCount(String strInput, int[] charCount)
{
for( int i = 0; i < strInput.length(); i++ )
{
charCount[ strInput.charAt(i)]++;
}
}

Then we iterate through the characters of the second string, we try to decrement the frequency of each character. If we found a zero, that means that particular character has appeared more number of times in the second string, then we can say that they are not anagrams. Otherwise we decrement the count of that character.

Finally we check the count array if they have any non-zero entries. If they are anagrams, we have all zero entries in count array. 

Note: We have considered the space also as a significant character in the above programs. So ‘school master’ can not be anagram of ‘the classroom’  even though they contain same letters. Also the input strings are case-sensitive.