How do you check if two strings are anagrams?
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.