Anagram Program in C

What is Anagram in String ?

We call a string anagram of another string if both the strings have the same characters with the same number of occurrences, but their order may be different in the strings.

For example, "hello" and "olleh" strings are anagrams of each other. This is because both the strings have the same characters ('h', 'e', 'l', 'o') with the same number of occurrences, $i.e.$, both strings have single occurrences of 'h', 'e' and 'o' and two occurrences of character 'l'.

But if we have two different strings like "hello" and "mello", which have a different set of characters that do not occur in another string, then such strings are not anagrams to one another.

Algorithm of the Anagram String

There are different algorithms to find whether two strings are anagrams in C.

Method 1 : Using Character Count Array

1. Input two strings from the user and assign them to variables.
2. Check if two strings have the same length. If the length of both strings is not equal, then the two strings are not anagrams.
3. If the strings have equal length, convert all upper-case characters to lower-case characters to make the comparison easier.
4. Convert the string to a character array that stores the frequency of all the lower-case characters.
5. Compare the two arrays. If they are equal, then the two strings are anagrams.

Because we are iterating once on the string to count occurrences of characters present in the string, this method has $O(n)$ time complexity and $O(26)$ space complexity as we are storing the character count of all the 26 English alphabets.

Method 2 : Using Sorting

1. Input two strings from the user and assign them to variables.
2. Check if two strings have the same length. If the length of both strings is not equal, then the two strings are not anagrams.
3. Sort both strings in lexicographical order.
4. Compare both the strings, and if they are equal, then both the strings are anagrams of each other.

Now that we have discussed two algorithms to check whether two strings are anagrams to each other, let us see their anagram program in C.

Examples of Anagram Program in C

1. Program to Check the Anagram of the String Using Nested for Loop

This method counts the frequency of each character from a to z and stores its count in a frequency array. The count of character 'a' is stored in index 0, character ‘b’ in 1st index, etc. Later this frequency of characters array is compared with the frequency of characters array of another string calculated with the same method. If they are identical, then both the strings are anagrams of each other. An anagram program in C for this approach is mentioned below.

Output :

Here, two arrays, freq_a and freq_b, are used to store the character occurrences of the first and second strings, respectively. In this approach, we assume that both the strings only have lower case characters, so we are not converting upper case characters to lower case characters. Once the frequency array is evaluated, we compare the character count of both the arrays, and if they are the same for all characters (‘a’ to ‘z’), then both the strings are anagrams of each other.

2. Program to Sort the String and Check the Anagram of the Strings

One way to check the anagram of the string is to sort both the strings and compare these two sorted strings. This approach works because when a string is sorted, the original order of characters in the string is lost, and characters are arranged in lexicographical format (lexicographical order is arranging the words in the order in which words appear in the dictionary).

For example, if the two strings ‘hello’ and ‘oellh’ are sorted, they both become ‘ehllo’, which indicates they are anagrams of each other. Let us see the anagram program in C for this approach.

Output :

Here, the function sortArr() is used to sort the string in lexicographical order using the bubble sort algorithm. Once both the strings are sorted, we can easily compare them using a for loop to find whether they are equal.

3. Program to Check the Anagram of the String Using a User-Defined Function

To check whether two strings are anagrams, we can create a user-defined function that takes two character arrays (strings) as input and returns an integer value to indicate if the strings are anagrams to each other.

Output :

In the above example, we are creating two arrays to store the character count of both strings. Before updating the character count array, we check whether the character in the string is uppercase and convert the upper case characters to lower case if the character is in the upper case. Once both the character count array is updated, we compare both arrays to check whether the character count is equal in both the strings. The function returns 1 if both the strings are anagrams of each other. Otherwise, the function returns integer 0.

4. Program to Check the Anagram of the String Using the Frequency of Characters

In the first method, we created two frequency arrays and then compared them to find whether the two strings were anagrams or not. We can optimize this approach further by using only one frequency array instead of two. Let us see how.

Output :

Here, we are incrementing the frequency count if a character is encountered from the first string and decrementing the frequency count if a character is from the second string. This way, for two strings to be anagram to one another after iterating both the strings, the frequency array should be 0 for all indexes. If not, then both the strings are not anagrams of each other.