SyntaxPilot
Courses/C Coding Questions/Lesson 17
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 17 of 30

String questions III

anagram check (counting array)first non-repeating characterfrequency of every character

These are the notes for C Coding Questions, episode 17, placement practice for people who finished the SyntaxPilot C course. String questions, part three: are two words anagrams?, the first character that never repeats, and the frequency of every character. One idea solves all three: the counting array.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real. In the input lines below, ⏎ means pressing Enter. Timings are from our machine.

Real-life pictures

In real life In C
a class monitor election: a tally mark next to each name on the blackboard the counting array: one box per character, count[c]++
two hands of cards: the same cards in a different order? anagram: the same counts
the first sock out of the laundry that has no pair first non-repeating: the first char whose count is 1
reading out the final tally: every name once, with its votes frequency: print each box once

The idea: a counting array

A counting array (also called a frequency table) has one box per possible character, all starting at 0:

int count[26] = {0};    /* letters 'a'..'z' only */
int count[256] = {0};   /* any char: one box per byte value */

= {0} sets every element to 0 (the first explicitly, the rest because missing initialisers are zero). A local array without it starts with whatever garbage was in memory.

Which box does a character go in? The value itself is the index:

  • small letters have consecutive codes, so c - 'a' is 0 for 'a', 1 for 'b' … 25 for 'z'. Use it only after checking isalpha and lowering with tolower; 'L' - 'a' is −21, an index outside the array.
  • any char: (unsigned char)c, 0..255. A plain char can be negative (on x86 it is signed), and a negative index is outside the array. gcc's -Wall warns about indexing with a plain char (-Wchar-subscripts).

Using the value itself to find its box is the simplest form of hashing.

#include <stdio.h>

int main() {
    char s[] = "banana";
    int count[26] = {0};
    for (int i = 0; s[i] != '\0'; i++)
        count[s[i] - 'a']++;
    for (int k = 0; k < 26; k++)
        if (count[k] > 0) printf("%c: %d\n", 'a' + k, count[k]);
    return 0;
}

Output:

a: 3
b: 1
n: 2

Q1: Are two words anagrams?

Problem. Two words are anagrams if they use the same letters, each the same number of times, in any order. Read pairs of words and print YES or NO; capital letters count as small ones.

Think out loud.

  • Input: pairs of words. Output: YES/NO per pair.
  • listen silent → YES, chai chat → NO, aab abb → NO (two a's vs one), Listen Silent → YES.
  • Edge cases: repeated letters, capitals, different lengths.

scanf("%99s %99s", a, b) reads two words and returns how many it stored; == 2 keeps going while it gets both.

The obvious attempt: is every letter of a somewhere in b?

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

int is_anagram(const char a[], const char b[]) {
    if (strlen(a) != strlen(b)) return 0;
    for (int i = 0; a[i] != '\0'; i++)
        if (strchr(b, a[i]) == NULL) return 0;
    return 1;
}

int main() {
    char a[100], b[100];
    while (scanf("%99s %99s", a, b) == 2)
        printf("%s %s: %s\n", a, b, is_anagram(a, b) ? "YES" : "NO");
    return 0;
}

Input listen silent⏎ aab abb⏎ chai chat⏎ Listen Silent⏎:

listen silent: YES
aab abb: YES
chai chat: NO
Listen Silent: NO

Why. strchr only asks whether a letter is present, not how many times: both a's of aab find the single a of abb. And 'L' isn't 'l', so Listen Silent fails. It is also O(n²): strchr walks b for every letter of a.

The fix: count, add for a, subtract for b

Add 1 to a letter's box for every letter of a, subtract 1 for every letter of b. They are anagrams exactly when every box ends at 0. Different lengths always leave some box non-zero, so no length check is needed. Only letters are counted (isalpha), lowered with tolower, so the index is always 0..25.

#include <stdio.h>
#include <ctype.h>

int is_anagram(const char a[], const char b[]) {
    int count[26] = {0};
    for (int i = 0; a[i] != '\0'; i++) {
        unsigned char c = a[i];
        if (isalpha(c)) count[tolower(c) - 'a']++;
    }
    for (int i = 0; b[i] != '\0'; i++) {
        unsigned char c = b[i];
        if (isalpha(c)) count[tolower(c) - 'a']--;
    }
    for (int k = 0; k < 26; k++)
        if (count[k] != 0) return 0;
    return 1;
}

int main() {
    char a[100], b[100];
    while (scanf("%99s %99s", a, b) == 2)
        printf("%s %s: %s\n", a, b, is_anagram(a, b) ? "YES" : "NO");
    return 0;
}

Same input:

listen silent: YES
aab abb: NO
chai chat: NO
Listen Silent: YES

More tests, Dormitory dirtyroom⏎ a b⏎ abc abcd⏎:

Dormitory dirtyroom: YES
a b: NO
abc abcd: NO

Time O(n): one pass over each word plus 26 checks. Space O(1): 26 boxes, whatever the length.

Another way: sort both words

Sort the letters of both words and compare: listen → eilnst, silent → eilnst. It works, but sorting is O(n log n) and changes the words (copy them first).

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

int cmp_char(const void *x, const void *y) {
    return *(const char *)x - *(const char *)y;
}

int main() {
    char a[100], b[100];
    while (scanf("%99s %99s", a, b) == 2) {
        char x[100], y[100];
        strcpy(x, a);
        strcpy(y, b);
        qsort(x, strlen(x), 1, cmp_char);
        qsort(y, strlen(y), 1, cmp_char);
        printf("%s %s: %s (%s, %s)\n", a, b, strcmp(x, y) == 0 ? "YES" : "NO", x, y);
    }
    return 0;
}

Input listen silent⏎ aab abb⏎:

listen silent: YES (eilnst, eilnst)
aab abb: NO (aab, abb)

(Subtracting two chars in the comparator is safe: both are small, so the result can't overflow. This version is case-sensitive; lower both words first for Listen Silent.)

Q2: First non-repeating character

Problem. Find the first character (from the left) that appears exactly once in the whole word. Print it and its index, or none.

Think out loud.

  • swiss → 'w' at 1, aabbc → 'c' at 4, programming → 'p' at 0, abab → none, aabbcc → none.
  • Edge cases: no answer at all, the answer at the end, repeats that are far apart.

The obvious attempt: look only to the right

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

int first_unique(const char s[]) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        int seen_again = 0;
        for (int j = i + 1; j < n; j++)
            if (s[j] == s[i]) seen_again = 1;
        if (!seen_again) return i;
    }
    return -1;
}

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        int i = first_unique(s);
        if (i == -1) printf("%s: none\n", s);
        else printf("%s: '%c' at index %d\n", s, s[i], i);
    }
    return 0;
}

Input swiss⏎ aabbc⏎ abab⏎ programming⏎ aabbcc⏎:

swiss: 'w' at index 1
aabbc: 'a' at index 1
abab: 'a' at index 2
programming: 'p' at index 0
aabbcc: 'a' at index 1

Why. At i = 1 in aabbc nothing to the right is an 'a', so it returns 'a'; the other 'a' is on the left, at index 0, and was never checked.

Fix one: count in the whole word (correct, but O(n²))

Count s[i] with j from 0 to n − 1; the first i with count 1 is the answer. Every character is compared with every other: n × n. Measured on 60,000 characters (a..z repeated, then '{' once at the very end):

#include <stdio.h>
#include <time.h>

#define N 60000
char s[N + 1];

double secs(clock_t start) {
    return (double)(clock() - start) / CLOCKS_PER_SEC;
}

int nested_way(const char s[], int n) {
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++)
            if (s[j] == s[i]) count++;
        if (count == 1) return i;
    }
    return -1;
}

int counting_way(const char s[], int n) {
    int count[256] = {0};
    for (int i = 0; i < n; i++) count[(unsigned char)s[i]]++;
    for (int i = 0; i < n; i++)
        if (count[(unsigned char)s[i]] == 1) return i;
    return -1;
}

int main() {
    for (int i = 0; i < N - 1; i++) s[i] = 'a' + i % 26;
    s[N - 1] = 'z' + 1;   /* '{' appears once, at the very end */
    clock_t t = clock();
    int a = nested_way(s, N);
    printf("nested:   index %d, %.2f s\n", a, secs(t));
    t = clock();
    int b = counting_way(s, N);
    printf("counting: index %d, %.2f s\n", b, secs(t));
    return 0;
}

Output (timings from our machine):

nested:   index 59999, 1.13 s
counting: index 59999, 0.00 s

Ten times longer would take about a hundred times longer for the nested way.

The fix: count first, then look

Pass 1 tallies every char into count[256]. Pass 2 walks the word from the left (not the boxes) and returns the first i with count[s[i]] == 1, so it really is the first one.

#include <stdio.h>

int first_unique(const char s[]) {
    int count[256] = {0};
    for (int i = 0; s[i] != '\0'; i++)
        count[(unsigned char)s[i]]++;
    for (int i = 0; s[i] != '\0'; i++)
        if (count[(unsigned char)s[i]] == 1) return i;
    return -1;
}

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        int i = first_unique(s);
        if (i == -1) printf("%s: none\n", s);
        else printf("%s: '%c' at index %d\n", s, s[i], i);
    }
    return 0;
}

Same input:

swiss: 'w' at index 1
aabbc: 'c' at index 4
abab: none
programming: 'p' at index 0
aabbcc: none

Time O(n): two passes. Space O(1): 256 boxes.

Q3: Frequency of every character

Problem. Print every character that appears, once each, with how many times it appears.

Think out loud.

  • banana → a=3 b=1 n=2; programming has 8 different letters, and g, m, r appear twice.
  • Edge cases: every char exactly once in the output; a one-letter word.

The obvious attempt: count and print for every position

#include <stdio.h>

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        printf("%s:", s);
        for (int i = 0; s[i] != '\0'; i++) {
            int count = 0;
            for (int j = 0; s[j] != '\0'; j++)
                if (s[j] == s[i]) count++;
            printf(" %c=%d", s[i], count);
        }
        printf("\n");
    }
    return 0;
}

Input programming⏎ banana⏎:

programming: p=1 r=2 o=1 g=2 r=2 a=1 m=2 m=2 i=1 n=1 g=2
banana: b=1 a=3 n=2 a=3 n=2 a=3

Why. The printf is inside the loop over positions: a char at three positions prints three times. And it is the O(n²) nested loop again.

The fix: tally, then walk the boxes

#include <stdio.h>

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        int count[256] = {0};
        for (int i = 0; s[i] != '\0'; i++)
            count[(unsigned char)s[i]]++;
        printf("%s:", s);
        for (int c = 0; c < 256; c++)
            if (count[c] > 0) printf(" %c=%d", c, count[c]);
        printf("\n");
    }
    return 0;
}

Same input:

programming: a=1 g=2 i=1 m=2 n=1 o=1 p=1 r=2
banana: a=3 b=1 n=2

The boxes are in code order, so the output is sorted by ASCII code. Time O(n + 256) = O(n), space O(1).

In order of first appearance

Walk the word; print a char's count, then set its box to 0, so the next time we meet it, it is skipped.

#include <stdio.h>

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        int count[256] = {0};
        for (int i = 0; s[i] != '\0'; i++)
            count[(unsigned char)s[i]]++;
        printf("%s:", s);
        for (int i = 0; s[i] != '\0'; i++) {
            unsigned char c = s[i];
            if (count[c] > 0) {
                printf(" %c=%d", c, count[c]);
                count[c] = 0;
            }
        }
        printf("\n");
    }
    return 0;
}

Same input:

programming: p=1 r=2 o=1 g=2 a=1 m=2 i=1 n=1
banana: b=1 a=3 n=2

Complexity summary

Task Method Time Space
anagram strchr for each letter O(n²), wrong with repeats and capitals O(1)
sort both, compare O(n log n) O(n) for the copies
count[26], ++ / -- O(n) O(1)
first non-repeating look right only O(n²), wrong O(1)
count in the whole word, nested O(n²) O(1)
count[256], two passes O(n) O(1)
frequency print per position, nested O(n²), repeats lines O(1)
count[256], walk the boxes O(n) O(1)

A fixed-size table (26 or 256 boxes) is O(1) space: it doesn't grow with the input. If the "characters" could be anything (say, any int), you'd need a real hash table instead.

Common mistakes (and the real results)

Mistake What you see Why Fix
strchr(b, a[i]) for each letter no error: aab abb: YES presence, not count count[26]: ++ for a, -- for b
count[s[i] - 'a']++ on Listen no warning: 'L' - 'a' = −21, writes outside the array (undefined behaviour) capitals and symbols aren't 'a'..'z' isalpha, then tolower(c) - 'a'
int count[26]; (no = {0}) no error: random counts a local array starts with garbage int count[26] = {0};
count[s[i]]++ with a plain char warning: array subscript has type 'char' [-Wchar-subscripts] a char can be negative count[(unsigned char)s[i]]++
look only to the right of i no error: aabbc: 'a' the copy on the left is missed count first, then look
print inside the position loop no error: r=2 printed twice one line per position walk the boxes, or zero the box after printing
walking the boxes for "first non-repeating" no error: the smallest unique char, not the first box order isn't word order pass 2 walks the word

The char subscript warning for real:

#include <stdio.h>

int main() {
    char s[] = "ab";
    int count[256] = {0};
    for (int i = 0; s[i] != '\0'; i++)
        count[s[i]]++;
    printf("%d %d\n", count['a'], count['b']);
    return 0;
}

Compiler output:

main.c: In function 'main':
main.c:7:16: warning: array subscript has type 'char' [-Wchar-subscripts]
    7 |         count[s[i]]++;
      |               ~^~~

Your turn: the most frequent character (solution)

Problem. Print the character that appears the most and how many times; on a tie, the smallest character. banana → a 3; programming → g 2 (g, m and r tie at 2).

Idea. Tally into count[256], then walk the boxes and keep the biggest, like the largest element in episode 7. Walking the boxes from 0 up and replacing only on a strictly bigger count gives the smallest char on a tie. O(n) time, O(1) space.

Show the solution
#include <stdio.h>

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        int count[256] = {0};
        for (int i = 0; s[i] != '\0'; i++)
            count[(unsigned char)s[i]]++;
        int best = 0;
        for (int c = 1; c < 256; c++)
            if (count[c] > count[best]) best = c;
        printf("%s: %c %d\n", s, best, count[best]);
    }
    return 0;
}

Input banana⏎ programming⏎ x⏎ mississippi⏎:

banana: a 3
programming: g 2
x: x 1
mississippi: i 4

(best starts at box 0, the '\0' box, whose count is 0; any real character beats it.)

Practice questions (with solutions)

1. Is a sentence a pangram? A pangram uses all 26 letters at least once.

Solution
#include <stdio.h>
#include <ctype.h>

int main() {
    char s[200];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int seen[26] = {0}, distinct = 0;
        for (int i = 0; s[i] != '\0'; i++) {
            unsigned char c = s[i];
            if (isalpha(c) && !seen[tolower(c) - 'a']) {
                seen[tolower(c) - 'a'] = 1;
                distinct++;
            }
        }
        printf("%d letters: %s\n", distinct, distinct == 26 ? "pangram" : "not a pangram");
    }
    return 0;
}

Input The quick brown fox jumps over the lazy dog⏎ Hello World⏎:

26 letters: pangram
7 letters: not a pangram

2. Remove duplicate characters, keeping the first of each. A seen table plus the read/write indexes from episode 16.

Solution
#include <stdio.h>

void remove_dups(char s[]) {
    int seen[256] = {0}, j = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        unsigned char c = s[i];
        if (!seen[c]) {
            seen[c] = 1;
            s[j++] = s[i];
        }
    }
    s[j] = '\0';
}

int main() {
    char s[100];
    while (scanf("%99s", s) == 1) {
        remove_dups(s);
        printf("%s\n", s);
    }
    return 0;
}

Input programming⏎ banana⏎ aaaa⏎:

progamin
ban
a

3. Anagrams ignoring spaces: dirty room and dormitory. Read two lines with fgets; the Q1 function already skips anything that isn't a letter.

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

int is_anagram(const char a[], const char b[]) {
    int count[26] = {0};
    for (int i = 0; a[i] != '\0'; i++) {
        unsigned char c = a[i];
        if (isalpha(c)) count[tolower(c) - 'a']++;
    }
    for (int i = 0; b[i] != '\0'; i++) {
        unsigned char c = b[i];
        if (isalpha(c)) count[tolower(c) - 'a']--;
    }
    for (int k = 0; k < 26; k++)
        if (count[k] != 0) return 0;
    return 1;
}

int main() {
    char a[100], b[100];
    while (fgets(a, sizeof a, stdin) != NULL && fgets(b, sizeof b, stdin) != NULL) {
        a[strcspn(a, "\n")] = '\0';
        b[strcspn(b, "\n")] = '\0';
        printf("\"%s\" / \"%s\": %s\n", a, b, is_anagram(a, b) ? "YES" : "NO");
    }
    return 0;
}

Input dirty room⏎ Dormitory⏎ School master⏎ The classroom⏎ chai⏎ tea⏎:

"dirty room" / "Dormitory": YES
"School master" / "The classroom": YES
"chai" / "tea": NO

Quick quiz

#include <stdio.h>

int main() {
    char s[] = "banana";
    int count[26] = {0};
    for (int i = 0; s[i] != '\0'; i++)
        count[s[i] - 'a']++;
    printf("%d %d %d\n", count[0], count[1], count['n' - 'a']);
    return 0;
}

(A) 1 2 3 (B) 3 1 2 (C) 3 2 1 (D) 0 1 2

Answer

(B) 3 1 2. Box 0 is 'a' (3 times), box 1 is 'b' (once), and 'n' - 'a' = 13 is the box for 'n' (twice).

3 1 2

Interview questions

  1. Check whether two strings are anagrams in O(n). A 26- (or 256-) box counting array: ++ for one, -- for the other, all zero.
  2. Why is strchr for each letter not enough? It checks presence, not counts; aab/abb pass.
  3. Sorting vs counting for anagrams? Sorting O(n log n) and changes the data; counting O(n) with O(1) extra space.
  4. First non-repeating character in O(n). Count, then a second pass over the string (not the table).
  5. Why is a 256-int table O(1) space? Its size doesn't depend on n.
  6. Why cast to unsigned char before indexing? A char can be negative; a negative index is out of bounds.
  7. What does int count[26] = {0}; do? Sets all 26 elements to 0.
  8. Print each character's frequency once. Walk the table, or print and zero the box while walking the string.
  9. What if the input can be any integers, not chars? A hash table (or sort), because a direct table would be too big.

Glossary

Term Meaning Example
Counting array (frequency table) An array with one counter per possible value int count[26] = {0};
Frequency How many times something appears 'a' in banana: 3
Tally Adding one to a counter for each item seen count[c]++
= {0} Initialises every element of an array to 0 int seen[256] = {0};
Garbage value Whatever was left in memory; an uninitialised local has it int count[26];
c - 'a' The letter's position in the alphabet, 0..25 'd' - 'a' = 3
(unsigned char)c The char's byte value, 0..255, safe as an index count[(unsigned char)c]
Hashing Using a value to compute where it is stored the char is its own box
Anagram Same letters, same counts, any order listen / silent
Non-repeating Appears exactly once 'w' in swiss
Pangram Uses every letter of the alphabet The quick brown fox…
strchr(s, c) Pointer to the first c in s, or NULL strchr("abb", 'a')
qsort The C library sort, with a comparator (episode 14) qsort(x, n, 1, cmp_char)
Comparator A function that says which of two items comes first cmp_char
Nested loop A loop inside a loop: n × n steps comparing every pair
O(n²) / O(n log n) / O(n) Work grows like n×n / like sorting / like n nested / sort / counting
Two passes Walking the data twice, still O(n) count, then look
-Wchar-subscripts gcc warning (in -Wall) for indexing with a plain char count[s[i]]
Undefined behaviour (UB) The C standard makes no promise about the result count['L' - 'a']
scanf return value How many items it stored; EOF at the end == 2 for two words

Summary

  • A counting array has one box per character and starts at = {0}; letters go to tolower(c) - 'a', any char to (unsigned char)c.
  • Anagram: ++ for one word, -- for the other, every box zero. strchr misses counts; sorting works in O(n log n).
  • First non-repeating: count, then walk the word for the first count of 1. Looking only right is wrong; counting with a nested loop is O(n²).
  • Frequency: tally, then walk the boxes (sorted) or print-and-zero while walking the word (first-appearance order). All O(n) time, O(1) space.

Next episode: String questions IV: write your own strcpy, strcmp and strcat; string to integer (atoi) with sign, spaces, invalid input and overflow.