Anagram Check Techniques in DSA C

Mental Model

Two words are anagrams if they have the exact same letters in the same amounts, just mixed up.

Analogy: Imagine two bags of colored beads. If both bags have the same colors and the same number of each color, they are anagrams, even if the beads are arranged differently.

word1: c a t
word2: t a c

Both have letters: c, a, t
Order can differ but counts must match.

Dry Run Walkthrough

Input: word1: "listen", word2: "silent"

Goal: Check if "listen" and "silent" are anagrams by comparing letter counts

Step 1: Count letters in "listen"

l:1, i:1, s:1, t:1, e:1, n:1

Why: We need to know how many times each letter appears in the first word

Step 2: Count letters in "silent"

s:1, i:1, l:1, e:1, n:1, t:1

Why: We count letters in the second word to compare with the first

Step 3: Compare letter counts of both words

Both have l:1, i:1, s:1, t:1, e:1, n:1

Why: If counts match exactly, words are anagrams

Result:

Words are anagrams because letter counts match exactly.

Annotated Code

DSA C

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

#define CHAR_RANGE 256

bool areAnagrams(const char *str1, const char *str2) {
    int count[CHAR_RANGE] = {0};
    int i;

    // If lengths differ, cannot be anagrams
    if (strlen(str1) != strlen(str2))
        return false;

    // Count letters in str1
    for (i = 0; str1[i] != '\0'; i++) {
        count[(unsigned char)str1[i]]++;
    }

    // Subtract counts using str2
    for (i = 0; str2[i] != '\0'; i++) {
        count[(unsigned char)str2[i]]--;
        // If count goes negative, str2 has extra letter
        if (count[(unsigned char)str2[i]] < 0)
            return false;
    }

    // All counts matched
    return true;
}

int main() {
    const char *word1 = "listen";
    const char *word2 = "silent";

    if (areAnagrams(word1, word2))
        printf("%s and %s are anagrams\n", word1, word2);
    else
        printf("%s and %s are NOT anagrams\n", word1, word2);

    return 0;
}

if (strlen(str1) != strlen(str2))

Check if lengths differ -- quick reject if not equal

for (i = 0; str1[i] != '\0'; i++) { count[(unsigned char)str1[i]]++; }

Count each letter in first word

for (i = 0; str2[i] != '\0'; i++) { count[(unsigned char)str2[i]]--; if (count[(unsigned char)str2[i]] < 0) return false; }

Subtract letter counts using second word and check for mismatch

return true;

If no mismatch found, words are anagrams

Output

listen and silent are anagrams

Complexity Analysis

Time: O(n) because we count letters in both words once, where n is word length

Space: O(1) because the count array size is fixed (256) regardless of input size

vs Alternative: Sorting both words takes O(n log n), so counting letters is faster and more efficient

Edge Cases

Empty strings

Returns true because two empty strings have matching letter counts

DSA C

if (strlen(str1) != strlen(str2))

Different lengths

Returns false immediately since lengths differ

DSA C

if (strlen(str1) != strlen(str2))

Same letters but different counts (e.g., "aabb" and "aaab")

Returns false because counts mismatch during subtraction

DSA C

if (count[(unsigned char)str2[i]] < 0) return false;

When to Use This Pattern

When you need to check if two words have the same letters in any order, use letter counting to quickly compare their character frequencies.

Common Mistakes

Mistake: Only sorting one word and comparing to the other without sorting it
Fix: Sort both words or use counting for both to ensure accurate comparison

Summary

Checks if two words have the same letters in the same amounts regardless of order.

Use when you want to verify if two strings are anagrams efficiently.

Counting letters and comparing counts is faster than sorting both strings.