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 checkingisalphaand lowering withtolower;'L' - 'a'is −21, an index outside the array. - any char:
(unsigned char)c, 0..255. A plaincharcan be negative (on x86 it is signed), and a negative index is outside the array. gcc's-Wallwarns about indexing with a plainchar(-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;programminghas 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
- Check whether two strings are anagrams in O(n). A 26- (or 256-) box counting array: ++ for one, -- for the other, all zero.
- Why is
strchrfor each letter not enough? It checks presence, not counts;aab/abbpass. - Sorting vs counting for anagrams? Sorting O(n log n) and changes the data; counting O(n) with O(1) extra space.
- First non-repeating character in O(n). Count, then a second pass over the string (not the table).
- Why is a 256-int table O(1) space? Its size doesn't depend on n.
- Why cast to
unsigned charbefore indexing? Acharcan be negative; a negative index is out of bounds. - What does
int count[26] = {0};do? Sets all 26 elements to 0. - Print each character's frequency once. Walk the table, or print and zero the box while walking the string.
- 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 totolower(c) - 'a', any char to(unsigned char)c. - Anagram: ++ for one word, -- for the other, every box zero.
strchrmisses 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.