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).