Determine if two strings are anagrams or not.

Solution #1: If destruction of strings is allowed then we can sort the strings in O(n log n) time and then compare them in O(n) time.

Solution #2: If we have the luxury of using plenty of extra memory then we can create two arrays of size 256 and store the occurrence of all unique characters in both strings in each array and then compare the arrays. Here is a pretty straight forward code. Time complexity being O(n + n + 1) ~ O(n).

int areAnagrams(char* str1, char* str2)
{
    int i;
    int arr1[256] = {0,};
    int arr2[256] = {0,};

    int unique_char_1 = 0;
    int unique_char_2 = 0;
    char* ptr1 = str1;
    char* ptr2 = str2;

    while(*ptr1 != '\0')
    {
        if(arr1[*ptr1] == 0)
            unique_char_1++;

        arr1[*ptr1]++;
        ptr1++;
    }

    while(*ptr2 != '\0')
    {
        if(arr2[*ptr2] == 0)
            unique_char_2++;

        arr2[*ptr2]++;
        ptr2++;
    }

    if(unique_char_1 != unique_char_2)
        return 0;

    for(i=0; i<256; i++)
    {
        if(arr1[i] != arr2[i])
            return 0;
    }

    return 1;
}

Solution #3: The above code can also be written using just one array like this,

int areAnagrams(char* str1, char* str2)
{
    int arr[256] = {0,};

    int unique_char_1 = 0;
    int unique_char_2 = 0;

    char* ptr1 = str1;
    char* ptr2 = str2;

    while(*ptr1 != '\0')
    {
        if(arr[*ptr1] == 0)
            unique_char_1++;

        arr[*ptr1]++;
        ptr1++;
    }

    while(*ptr2 != '\0')
    {
        if(arr[*ptr2] == 0)
            return 0;

        arr[*ptr2]--;

        if(arr[*ptr2] == 0)
        {
            unique_char_2++;

            if(unique_char_1 == unique_char_2)
                return 1;
        }

        ptr2++;
    }

    return 0;
}