Anagram in C | Program and Explanation

In this article, we will discuss the problems related to anagram in C. Anagrams are a very interesting topic and we will discuss how to code in anagram in C. Let’s get started.

Before we start coding, let’s see the basics, the algorithm, and code for the same.

INTRODUCTION

What are anagrams?

Anagrams are nothing but a word or a phrase formed by rearranging the letters of a different word or phrase, using all the original letters all just once.

Examples

Let’s discuss a few examples of anagrams just to be clear of the definition.

Example using a single word:

  • Silent = Listen
  • Fried = Fired
  • Race = Care

Example for phrase:

  • The eyes = They see
  • Dormitory = Dirty room
  • A gentleman = Elegant man

PROBLEM

Difficult level: Easy

Suppose we have strings that say “silent” and “listen”, we print them are anagrams. If not we print they are not anagrams. This is the problem statement.

In the anagram problem we have variations, let’s discuss the algorithm and code for each one now.

Comparing the strings

The idea is we sort the strings in ascending order and then compare the sorted arrays. If they are equal then the strings are anagrams or else they are not anagrams. Now let’s see the code and its explanation.

Code

//pgm to if two strings are anagram or not
#include <stdio.h>
#include <string.h>
int main (void)
{
   char s1[] = "recitals";
   char s2[] = "articles";

   //variable used while sorting process
   char temp;

   int i, j;
   //finding the string lengths
   int n  = strlen(s1);
   int n1 = strlen(s2);

   // If both strings are of different length, then they are not anagrams

   if( n != n1) {    
      printf("%s and %s are not anagrams! \n", s1, s2);
      return 0;
   }
   
   // sorting both the strings
   for (i = 0; i < n-1; i++) 
  {
      for (j = i+1; j < n; j++)
          {
         if (s1[i] > s1[j]) {
            temp  = s1[i];
            s1[i] = s1[j];
            s1[j] = temp;
         }
         if (s2[i] > s2[j]) {
            temp  = s2[i];
            s2[i] = s2[j];
            s2[j] = temp;
         }
      }
   }

   // Compare both strings character by character

   for(i = 0; i<n; i++) {
      if(s1[i] != s2[i]) {    
         printf("Strings are not anagrams! \n", s1, s2);
         return 0;
      }
   }

   printf("Strings are anagrams! \n");
   return 0;
}

Run the code here

Code Explanation

  1. First, create two strings using arrays.
  2. Then find the length of both strings using the function strlen and then store it in two different variables.
  3. If the length is not the same, then print the output as NOT ANAGRAMS. Because, if two strings are of different lengths they can not be anagrams.
  4. Now our task is to sort both the arrays in ascending order.
  5. Run a for loop from 0 to till n-1.
  6. Again run a nested for loop from the range i+1 till n-1. (Here i+1 because we need to compare with the next character)
  7. Now sort the first string using a separate variable temp. (This array is used because we need to shift the characters using a temp variable).
  8. Sort the second array using the same technique.
  9. To compare the characters, run a for loop from 0 till n and check the condition using the if statement.
  10. Print the statement accordingly.

Output

output-anagram in c
Output as anagram

Complexity

Time Complexity

We sort the string first, so for the sort, the complexity is O(n). And then we perform a traversal process for checking, so complexity is O(n).

So, Time complexity = n*O(n) +O(n).

We leave out the constants, so total is O(n2).

Space Complexity

The space complexity is O(1) since it is a heap sort.

Calculating the frequency of characters

Here the idea is, we calculate the frequency of each character in both the strings and then store the count in an array of both the strings. Then we compare the frequency in the arrays and then get the result.

Code

// C program to check if the strings are anagrams or not

#include <stdio.h>

int check_anagram(char [], char []);

int main()
{
char a[100], b[100];

printf(“Enter two strings : \n”);
gets(a);
gets(b);

if (check_anagram(a, b) == 1)
printf(“The strings are anagrams\n”);
else
printf(“The strings are not anagrams\n”);

return 0;
}

int check_anagram(char a[], char b[])
{
int first[26] = {0}, second[26] = {0}, c=0;

// Calculating frequency of characters of first string

while (a[c] != ‘\0’)
{
first[a[c]-‘a’]++;
c++;
}

c = 0;

while (b[c] != ‘\0’)
{
second[b[c]-‘a’]++;
c++;
}

// Comparing frequency of characters

for (c = 0; c < 26; c++)
{
if (first[c] != second[c])
return 0;
}

return 1;
}

Run the code here

Code Explanation

  1. Create two arrays for two strings and get the input from the user.
  2. We write a separate function for checking the anagram condition, we return the value as 0 or 1. So, check which values mean anagrams and print them checking with the help of the IF statement.
  3. Now let’s see the explanation for the function. Inside the function create two arrays(first and second) of size 26(since we have only 26 alphabets) and set it as “zero”.
  4. Also, initialize a count variable c.
  5. Now run a while loop till the string is null. (Here it is like traversing the string as an array)
  6. Inside the loop, start initializing the array first by the frequency of alphabets. This is done by subtracting the first alphabet ‘a’.
  7. This is nothing but finding the ASCII value of the characters.
  8. Continue the same procedure for the second input string.
  9. Now check the ASCII value of both the arrays using a for loop.
  10. Now return the value 1 if the condition satisfies. Else, return 0.
  11. This value is checked in Main and the result is printed accordingly.

Output

Output for not anagram

Complexity

Time complexity

We use two while loops, so the complexity is O(nlogn). We also traverse one time, so O(n).

Time complexity =2*O(nlogn) +O(n). (we use two strings, so 2).

Leaving out the constants, we get total as O(nlogn).

Space Complexity

The space complexity can be O(n) if merge sort else, O(1).

Related problems

Numbers

Now, we will check if the two numbers are anagrams are not.

Here the idea is that we separate each of the digits in the number and then store them in an array. Afterward, we check if both the arrays are equal or not. Below is the implementation of this approach.

Code

//pgm for checking if numbers are anagrams are not
#include <stdio.h>
//function for updating the frequency
//function separates each of the digits and stores in array
void updateFreq(int n, int freq[]) 
{ 
    while (n)
    { 
        int digit = n % 10;     
        freq[digit]++; 
        n /= 10; 
    } 
}
//function for checking anagrams 
int areAnagrams(int a, int b) 
{ 
    int freqA[10] = { 0 }; 
    int freqB[10] = { 0 }; 
    updateFreq(a, freqA); 
    updateFreq(b, freqB); 
    for (int i = 0; i < 10; i++) { 
        if (freqA[i] != freqB[i]) 
            return 0; 
    } 
  
    return 1; 
} 
//driver code
void main() 
{ 
    int a = 240, b = 204; 
    if (areAnagrams(a, b)) 
        printf("They are anagrams"); 
    else
        printf("They are anagrams"); 
} 

Run the code here

Code Explanation

  1. We will write two separate functions
  2. The first function is for separating the digits and storing them in an array. To do this use a while loop and perform the modulo operation with 10. This makes us get the last digit separately.
  3. Now store this in an array.
  4. Divide the number by 10. This step is to leave out the last digit.
  5. Continue this process till the number becomes 0 in dividing. This means we have stored every separate digit in the array.
  6. The next function is for checking the anagram condition. Here we declare two separate arrays and call the above(first) function.
  7. Run a for loop and check if both the arrays are equal or not. Return an int accordingly
  8. In the driver code, just call the second function using the If statement and print the result accordingly.

Output

Output with numbers as anagram

Binary representation

Now, we will see if the binary representation of the two numbers are anagrams to each or other not. Let’s see an example first.

a =8, b=4 ——> they are anagrams because they have equal number of 0s and 1s.

a=4,b=5 ——-> not anagrams. See the picture below to get a clear idea.

Now we will see only the approaches of this problem .

Approach 1

First, convert each of the numbers into binary representation and then store them in two separate arrays. Then sort both the arrays. Now the arrays will be in a sorted way. Now compare each of the arrays and then decide the result accordingly.

Complexity

Time complexity

This has the complexity of O(nlogn). (Since this involves sorting. We have earlier discussed this).

Space complexity

Space complexity is 0(1).

Approach 2

This is one of the efficient ways of performing the anagram for numbers. This approach starts with the same as the same one. We start with converting the number into binary representation and storing them into two separate arrays. Now, our task is to count the number of 1s in both arrays. If the arrays are equal then, they are anagrams if not then they are not.

Complexity

Time complexity

This has the complexity of O(1). (Since this does not involve sorting)

Space complexity

Space complexity is 0(1). (No extra space is used)

Conclusion

In this article we have learnt about anagram in c. We also learnt about the possible variations in the anagram in c. Hope this article helped you learn all the basics in a easy manner. Grow by learning and happy coding!

Leave a Comment

Your email address will not be published. Required fields are marked *