Anagram Check Techniques in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sorting-Based Anagram Check

What is the output of this C code that checks if two strings are anagrams by sorting?

DSA C

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

int cmpfunc(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

int areAnagrams(char *str1, char *str2) {
    int n1 = strlen(str1);
    int n2 = strlen(str2);
    if (n1 != n2) return 0;
    qsort(str1, n1, sizeof(char), cmpfunc);
    qsort(str2, n2, sizeof(char), cmpfunc);
    for (int i = 0; i < n1; i++) {
        if (str1[i] != str2[i]) return 0;
    }
    return 1;
}

int main() {
    char s1[] = "listen";
    char s2[] = "silent";
    if (areAnagrams(s1, s2))
        printf("Anagrams\n");
    else
        printf("Not Anagrams\n");
    return 0;
}

A Not Anagrams

B Anagrams

C Compilation Error

D Runtime Error

💡 Hint

Check if sorting both strings results in identical sequences.

The code sorts both strings and compares them character by character. Since "listen" and "silent" have the same characters, the output is "Anagrams".

❓ Predict Output

intermediate

Output of Frequency Count Anagram Check

What is the output of this C code that checks if two strings are anagrams by counting character frequencies?

DSA C

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

int areAnagrams(char *str1, char *str2) {
    int count[256] = {0};
    int i;
    if (strlen(str1) != strlen(str2)) return 0;
    for (i = 0; str1[i] && str2[i]; i++) {
        count[(unsigned char)str1[i]]++;
        count[(unsigned char)str2[i]]--;
    }
    for (i = 0; i < 256; i++) {
        if (count[i] != 0) return 0;
    }
    return 1;
}

int main() {
    char s1[] = "triangle";
    char s2[] = "integral";
    if (areAnagrams(s1, s2))
        printf("Anagrams\n");
    else
        printf("Not Anagrams\n");
    return 0;
}

A Not Anagrams

B Compilation Error

C Segmentation Fault

D Anagrams

💡 Hint

Check if character counts balance out to zero.

The code counts characters in both strings. Since "triangle" and "integral" have the same characters, the counts balance and output is "Anagrams".

🧠 Conceptual

advanced

Time Complexity of Anagram Checks

Which option correctly states the time complexity of checking anagrams using sorting vs frequency counting for strings of length n?

A Sorting: O(n^2), Frequency counting: O(n^2)

B Sorting: O(n), Frequency counting: O(n log n)

C Sorting: O(n log n), Frequency counting: O(n)

D Sorting: O(log n), Frequency counting: O(n^2)

💡 Hint

Sorting usually takes more time than counting frequencies.

Sorting takes O(n log n) time, while frequency counting uses a fixed-size array and takes O(n) time.

🔧 Debug

advanced

Identify the Bug in Anagram Frequency Code

What error does this code produce when checking anagrams, and why?

DSA C

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

int areAnagrams(char *str1, char *str2) {
    int count[26] = {0};
    int i;
    if (strlen(str1) != strlen(str2)) return 0;
    for (i = 0; str1[i] && str2[i]; i++) {
        count[str1[i] - 'a']++;
        count[str2[i] - 'a']--;
    }
    for (i = 0; i < 26; i++) {
        if (count[i] != 0) return 0;
    }
    return 1;
}

int main() {
    char s1[] = "Listen";
    char s2[] = "Silent";
    if (areAnagrams(s1, s2))
        printf("Anagrams\n");
    else
        printf("Not Anagrams\n");
    return 0;
}

A Prints "Not Anagrams" due to case sensitivity

B Compilation error due to missing header

C Causes segmentation fault due to invalid array index

D Runs correctly and prints "Anagrams"

💡 Hint

Check how uppercase letters are handled in the code.

The code assumes lowercase letters only. Uppercase letters cause mismatches, so it prints "Not Anagrams".

🚀 Application

expert

Memory Usage in Anagram Checking

Which option best describes the memory usage difference between sorting-based and frequency-counting anagram checks for very long strings?

A Sorting uses O(n) extra memory, frequency counting uses O(1) fixed memory

B Sorting uses O(1) extra memory, frequency counting uses O(n) memory

C Both use O(n) extra memory equally

D Sorting uses O(n^2) memory, frequency counting uses O(n log n)

💡 Hint

Consider if sorting is done in-place and size of frequency array.

Sorting typically requires O(n) memory for the sort operation (depending on algorithm), frequency counting uses a fixed-size array (e.g., 256 ints) which is O(1).

Practice

1. What does it mean if two strings are anagrams of each other?

easy

A. They contain the same characters in any order

B. They have the same length but different characters

C. They start with the same character

D. They end with the same character

Solution

1. Step 1: Understand the definition of anagrams

   Anagrams are words or phrases made by rearranging the letters of another, so they must have the same characters.

2. Step 2: Compare the character sets

   If two strings have exactly the same characters, just in different orders, they are anagrams.

3. Final Answer:

   They contain the same characters in any order -> Option A

4. Quick Check:

   Anagrams = same characters [OK]

Hint: Anagrams have identical letters, order doesn't matter [OK]

Common Mistakes:

• Thinking length alone defines anagrams
• Assuming same start or end means anagram
• Ignoring character counts

2. Which of the following C code snippets correctly checks if two strings are anagrams by sorting?

easy

A. Check only first and last characters

B. Compare lengths only

C. Use strcmp directly without sorting

D. Sort both strings and compare with strcmp

Solution

1. Step 1: Understand sorting approach

   Sorting both strings puts their characters in order, so if they are anagrams, sorted strings will be identical.

2. Step 2: Use strcmp to compare sorted strings

   strcmp returns 0 if strings are equal, confirming anagram status.

3. Final Answer:

   Sort both strings and compare with strcmp -> Option D

4. Quick Check:

   Sort + strcmp = correct anagram check [OK]

Hint: Sort strings then compare to check anagrams [OK]

Common Mistakes:

• Comparing strings without sorting
• Ignoring length check before sorting
• Using strcmp on unsorted strings

3. What will be the output of the following C code snippet?

#include 
#include 
#include 

bool areAnagrams(char *str1, char *str2) {
    int count[256] = {0};
    int i;
    for (i = 0; str1[i] && str2[i]; i++) {
        count[(unsigned char)str1[i]]++;
        count[(unsigned char)str2[i]]--;
    }
    if (str1[i] || str2[i]) return false;
    for (i = 0; i < 256; i++) {
        if (count[i] != 0) return false;
    }
    return true;
}

int main() {
    if (areAnagrams("listen", "silent"))
        printf("Anagrams\n");
    else
        printf("Not Anagrams\n");
    return 0;
}

medium

A. Anagrams

B. Not Anagrams

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze character counting logic

   The function increments count for each char in str1 and decrements for str2. If strings are anagrams, counts balance to zero.

2. Step 2: Check string lengths and counts

   Strings "listen" and "silent" have same length and characters, so count array ends with all zeros, returning true.

3. Final Answer:

   Anagrams -> Option A

4. Quick Check:

   Balanced counts = anagrams [OK]

Hint: Count chars increment/decrement; zero counts mean anagrams [OK]

Common Mistakes:

• Not checking string length equality
• Ignoring unsigned char cast for indexing
• Returning true without count check

4. Identify the bug in this C function intended to check anagrams:

bool isAnagram(char *s1, char *s2) {
    int count[26] = {0};
    for (int i = 0; s1[i]; i++) {
        count[s1[i] - 'a']++;
        count[s2[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) return false;
    }
    return true;
}

medium

A. Missing semicolon in the first for loop

B. Uses int for loop variable instead of size_t

C. Does not check if strings have same length

D. Second loop starts from i=1 instead of i=0

Solution

1. Step 1: Check loop and length conditions

   The loop runs only while s1[i] is valid, but s2 may be shorter or longer, causing mismatch.

2. Step 2: Identify missing length check

   Without verifying s1 and s2 have same length, function may incorrectly return true or access invalid memory.

3. Final Answer:

   Does not check if strings have same length -> Option C

4. Quick Check:

   Length check missing = bug [OK]

Hint: Always check string lengths before counting chars [OK]

Common Mistakes:

• Assuming strings are always same length
• Ignoring null terminator in second string
• Not handling uppercase letters (less critical here)

5. Given two strings that may contain uppercase, lowercase, and spaces, which approach best checks if they are anagrams ignoring case and spaces?

hard

A. Sort strings directly including spaces and compare

B. Convert both to lowercase, remove spaces, then count characters

C. Compare lengths including spaces only

D. Check only first and last characters ignoring case

Solution

1. Step 1: Normalize strings by case and spaces

   Convert all letters to lowercase and remove spaces to compare only meaningful characters.

2. Step 2: Count characters or sort normalized strings

   After normalization, counting characters or sorting will correctly identify anagrams ignoring case and spaces.

3. Final Answer:

   Convert both to lowercase, remove spaces, then count characters -> Option B

4. Quick Check:

   Normalize case and spaces before checking [OK]

Hint: Normalize case and remove spaces before checking anagrams [OK]

Common Mistakes:

• Comparing strings with spaces included
• Ignoring case differences
• Assuming length check includes spaces