Check whether two strings are anagram of each other

Write a function to check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “abcd” and “dabc” are anagram of each other.

Method 1 (Use Sorting)
1) Sort both strings
2) Compare the sorted strings

• C/C++
• Python

// C/C++ program to check whether two strings are anagrams // of each other #include <stdio.h> #include <string.h>   /* Function prototype for string a given string using    quick sort */ void quickSort(char *arr, int si, int ei);   /* function to check whether two strings are anagram of    each other */ bool areAnagram(char *str1, char *str2) {     // Get lenghts of both strings     int n1 = strlen(str1);     int n2 = strlen(str2);       // If length of both strings is not same, then they     // cannot be anagram     if (n1 != n2)       return false;       // Sort both strings     quickSort(str1, 0, n1 - 1);     quickSort(str2, 0, n2 - 1);       // Compare sorted strings     for (int i = 0; i < n1;  i++)        if (str1[i] != str2[i])          return false;       return true; }   // Following functions (exchange and partition are needed // for quickSort) void exchange(char *a, char *b) {     char temp;     temp = *a;     *a   = *b;     *b   = temp; }   int partition(char A[], int si, int ei) {     char x = A[ei];     int i = (si - 1);     int j;       for (j = si; j <= ei - 1; j++)     {         if(A[j] <= x)         {             i++;             exchange(&A[i], &A[j]);         }     }     exchange (&A[i + 1], &A[ei]);     return (i + 1); }   /* Implementation of Quick Sort A[] --> Array to be sorted si  --> Starting index ei  --> Ending index */ void quickSort(char A[], int si, int ei) {     int pi;    /* Partitioning index */     if(si < ei)     {         pi = partition(A, si, ei);         quickSort(A, si, pi - 1);         quickSort(A, pi + 1, ei);     } }   /* Driver program to test to print printDups*/ int main() {     char str1[] = "test";     char str2[] = "ttew";     if (areAnagram(str1, str2))       printf("The two strings are anagram of each other");     else       printf("The two strings are not anagram of each other");       return 0; }

Output:

The two strings are not anagram of each other

Time Complexity: Time complexity of this method depends upon the sorting technique used. In the above implementation, quickSort is used which may be O(n^2) in worst case. If we use a O(nLogn) sorting algorithm like merge sort, then the complexity becomes O(nLogn)

Method 2 (Count characters)
This method assumes that the set of possible characters in both strings is small. In the following implementation, it is assumed that the characters are stored using 8 bit and there can be 256 possible characters.
1) Create count arrays of size 256 for both strings. Initialize all values in count arrays as 0.
2) Iterate through every character of both strings and increment the count of character in the corresponding count arrays.
3) Compare count arrays. If both count arrays are same, then return true.

• C
• Python

# include <stdio.h> # define NO_OF_CHARS 256   /* function to check whether two strings are anagram of    each other */ bool areAnagram(char *str1, char *str2) {     // Create 2 count arrays and initialize all values as 0     int count1[NO_OF_CHARS] = {0};     int count2[NO_OF_CHARS] = {0};     int i;       // For each character in input strings, increment count in     // the corresponding count array     for (i = 0; str1[i] && str2[i];  i++)     {         count1[str1[i]]++;         count2[str2[i]]++;     }       // If both strings are of different length. Removing this     // condition will make the program fail for strings like     // "aaca" and "aca"     if (str1[i] || str2[i])       return false;       // Compare count arrays     for (i = 0; i < NO_OF_CHARS; i++)         if (count1[i] != count2[i])             return false;       return true; }   /* Driver program to test to print printDups*/ int main() {     char str1[] = "geeksforgeeks";     char str2[] = "forgeeksgeeks";     if ( areAnagram(str1, str2) )       printf("The two strings are anagram of each other");     else       printf("The two strings are not anagram of each other");       return 0; }