</>EmbeddedInterview

How do you check if two strings are anagrams?

EasyArrays & Strings (Coding Round)

Short answer: Two strings are anagrams if they contain the same characters with the same counts. Count each character of the first string up and each character of the second down in a 256-entry table; they are anagrams if every count ends at zero. O(n) time, O(1) space (fixed table).

#include <stdbool.h>
#include <string.h>

bool is_anagram(const char *s1, const char *s2)
{
    if (strlen(s1) != strlen(s2)) return false;   /* quick reject */
    int freq[256] = {0};
    for (const char *p = s1; *p; p++) freq[(unsigned char)*p]++;
    for (const char *p = s2; *p; p++) freq[(unsigned char)*p]--;
    for (int i = 0; i < 256; i++)
        if (freq[i] != 0) return false;
    return true;
}
/* "listen", "silent" -> true */

The (unsigned char) cast is important. On most Arm Linux compilers char is unsigned, but on x86 and many others it is signed. A byte such as 0xE9 ('é' in Latin-1) is then -23, and freq[s1[i]] writes to freq[-23], outside the array. Casting to unsigned char keeps the index in 0..255.

Why check lengths first: it rejects most non-anagrams immediately. It is not required for correctness, because the counts would not all be zero anyway.

Alternatives

Method Time Space
Sort both, compare O(n log n) O(1)–O(n)
Count table O(n) O(256)
Product of primes O(n) O(1), but overflows quickly

Variants: ignore case and spaces (tolower, skip ' '), or only lowercase letters (int freq[26], index c - 'a'). "Group words that are anagrams of each other" uses the sorted word or the count signature as a hash key.