SyntaxPilot
Courses/C Coding Questions/Lesson 15
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 15 of 30

String questions I

string length without strlenreverse a string in placepalindrome string (ignoring case and spaces)

These are the notes for C Coding Questions, episode 15, placement practice for people who finished the SyntaxPilot C course. String questions, part one: the length of a string without strlen (and why sizeof is not the length), reversing a string in place with two pointers, and checking a palindrome while ignoring capitals, spaces and punctuation.

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, 64-bit size_t), the SyntaxPilot compiler's C command with warnings on, and every output below is real. In the input lines below, ⏎ means pressing Enter.

Real-life pictures

In real life In C
counting the letters on a name plate: stop where the name ends, don't measure the plate string length: count up to '\0', not sizeof
reading a train name board backwards: swap the ends, walk inwards reverse in place with two pointers
Nitin, "Never odd or even": the same from both ends palindrome, skipping spaces, ignoring case

First: what a string is in C

C has no string type. A string is a char array (an array of characters) that ends with the null terminator '\0', the character whose value is 0. Everything after it is ignored.

char s[100];          a box with room for 100 chars
s holds "Priya":      P  r  i  y  a  \0  ?  ?  ?  ...   (5 letters, 6 chars used)

fgets(s, sizeof s, stdin) reads one line (spaces included) into s: at most sizeof s - 1 characters, it keeps the '\n' from the Enter key if it fits, and always adds '\0'. At the end of the input it returns NULL, so while (fgets(...) != NULL) reads every line.

sizeof gives the size of a variable or type in bytes, as a size_t: an unsigned integer type (no negative values) made for sizes. Print it with %zu.

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

int main() {
    char s[100] = "Priya";
    printf("sizeof %zu, strlen %zu\n", sizeof(s), strlen(s));
    return 0;
}

Output:

sizeof 100, strlen 5

Q1: String length without strlen

Problem. Read lines of text and print the length of each (the number of characters before '\0', without the newline), without calling strlen.

Line Output
Priya 5
New Delhi 9 (the space counts)
(empty line) 0
Priya with no Enter at the end 5

Edge cases: spaces, an empty line, the '\n' that fgets keeps, a last line with no '\n'.

The obvious attempt: sizeof

#include <stdio.h>

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL)
        printf("length %d\n", sizeof(s));
    return 0;
}

Compiler output (it still compiles and runs):

warning: format '%d' expects argument of type 'int', but argument 2 has type 'long unsigned int' [-Wformat=]
    6 |         printf("length %d\n", sizeof(s));
      |                        ~^     ~~~~~~~~~
      |                         |     |
      |                         int   long unsigned int
      |                        %ld

Input Priya⏎ New Delhi⏎ ⏎:

length 100
length 100
length 100

Why. sizeof(s) is the size of the array (100 bytes), not of the text inside it, so it is 100 for every line. And sizeof gives a size_t (long unsigned int here), but %d expects an int: -Wall caught the wrong format. The fix for printing a size_t is %zu.

Second attempt: count up to '\0'

#include <stdio.h>

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int len = 0;
        while (s[len] != '\0') len++;
        printf("length %d\n", len);
    }
    return 0;
}

Same input:

length 6
length 10
length 1

Why. One too many every time: fgets keeps the newline. Priya⏎ is stored as P r i y a \n \0, and the empty line is just \n \0.

The fix: count, then remove the newline

#include <stdio.h>

int length(const char s[]) {
    int n = 0;
    while (s[n] != '\0') n++;
    return n;
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = length(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        printf("\"%s\" has length %d\n", s, n);
    }
    return 0;
}

const char s[] promises the function only reads the string. After counting, if (n > 0 && s[n - 1] == '\n') s[--n] = '\0'; overwrites the newline with '\0' and makes n one smaller. The n > 0 check protects the empty string, and a last line without a newline is left alone.

Input Priya⏎ New Delhi⏎ ⏎:

"Priya" has length 5
"New Delhi" has length 9
"" has length 0

Input Priya (no Enter at the end):

"Priya" has length 5

Complexity: O(n) time (one look at each character), O(1) space. A line longer than 98 characters is read by fgets in pieces of up to 99; make the array bigger for longer lines.

Q2: Reverse a string in place

Problem. Reverse each line in place: inside the same array, without a second array (only a few extra variables).

Line Output
chai iahc
Mumbai iabmuM
a a
(empty) (empty)
New Delhi ihleD weN

Edge cases: odd and even length, one character, an empty line, spaces. From here on we use strlen from <string.h>: it counts exactly like our length.

The obvious attempt: swap every i with its mirror

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

void reverse(char s[], int n) {
    for (int i = 0; i < n; i++) {
        char t = s[i];
        s[i] = s[n - 1 - i];
        s[n - 1 - i] = t;
    }
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        reverse(s, n);
        printf("\"%s\"\n", s);
    }
    return 0;
}

Input chai⏎ Mumbai⏎ a⏎ ⏎ New Delhi⏎:

"chai"
"Mumbai"
"a"
""
"New Delhi"

Why. Nothing changed. By the middle the string is already reversed, and the second half of the loop swaps every pair back:

i = 0: c h a i -> i h a c
i = 1: i h a c -> i a h c     reversed
i = 2: i a h c -> i h a c     (swaps i=1 and j=2 back)
i = 3: i h a c -> c h a i     (swaps i=0 and j=3 back)

The fix: two pointers that stop in the middle

Two pointers: one index i from the left end, one j from the right end. Swap s[i] and s[j], move them towards each other, stop when they meet: while (i < j). That's n / 2 swaps; with an odd length the middle character stays.

"chai":  i=0 j=3  swap c,i -> i h a c
         i=1 j=2  swap h,a -> i a h c
         i=2 j=1  i > j: stop (2 swaps)
#include <stdio.h>
#include <string.h>

void reverse(char s[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
        i++;
        j--;
    }
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        reverse(s, n);
        printf("\"%s\"\n", s);
    }
    return 0;
}

Same input:

"iahc"
"iabmuM"
"a"
""
"ihleD weN"

Complexity: O(n) time (n / 2 swaps), O(1) extra space.

One more slip: j = n

Change int i = 0, j = n - 1; to int i = 0, j = n; and run the same input:

""
""
""
""
""

s[n] is the '\0'. The first swap moves it to index 0, and a string whose first char is '\0' is empty. The last character is s[n - 1].

Not in place: reverse into a second array

This works too, but uses O(n) extra space for r, which the question did not allow:

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

int main() {
    char s[100], r[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        for (int i = 0; i < n; i++) r[i] = s[n - 1 - i];
        r[n] = '\0';
        printf("\"%s\" -> \"%s\"\n", s, r);
    }
    return 0;
}

Input chai⏎ Mumbai⏎:

"chai" -> "iahc"
"Mumbai" -> "iabmuM"

Q3: Palindrome, ignoring case and spaces

Problem. A palindrome reads the same forwards and backwards. For each line print YES or NO, ignoring capital letters, spaces and punctuation.

Line Output
madam YES
Nitin YES
Never odd or even YES
A man, a plan, a canal: Panama YES
chai NO
(empty) / only spaces YES (nothing differs)
ab NO

Edge cases: capitals, spaces, commas and colons, an empty line, a line of only spaces.

The obvious attempt: compare the raw chars

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

int is_pal(const char s[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        if (s[i] != s[j]) return 0;
        i++;
        j--;
    }
    return 1;
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        printf("\"%s\": %s\n", s, is_pal(s, n) ? "YES" : "NO");
    }
    return 0;
}

Input madam⏎ Nitin⏎ Never odd or even⏎:

"madam": YES
"Nitin": NO
"Never odd or even": NO

Why. A char is stored as a number, its ASCII code: 'N' is 78 and 'n' is 110, so they are different characters.

Second attempt: compare with tolower

tolower(c) from <ctype.h> turns a capital letter into the small one and returns every other character unchanged. Pass it (unsigned char)c: a plain char can be negative for some characters, and passing a negative value (other than EOF) to the <ctype.h> functions is undefined behaviour.

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

int is_pal(const char s[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j]))
            return 0;
        i++;
        j--;
    }
    return 1;
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        printf("\"%s\": %s\n", s, is_pal(s, n) ? "YES" : "NO");
    }
    return 0;
}

Same input:

"madam": YES
"Nitin": YES
"Never odd or even": NO

Why. The letters match, but the spaces are in different places:

index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
        N e v e r _ o d d _ o  r  _  e  v  e  n
i = 4 is 'r', but j = 12 is ' '  ->  NO

The fix: skip what isn't a letter or digit

isalnum(c) (is alphanumeric, also in <ctype.h>) is true for a letter or a digit. If s[i] isn't one, move i right; if s[j] isn't, move j left; only then compare. continue jumps back to the while check.

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

int is_pal(const char s[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        if (!isalnum((unsigned char)s[i])) { i++; continue; }
        if (!isalnum((unsigned char)s[j])) { j--; continue; }
        if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j]))
            return 0;
        i++;
        j--;
    }
    return 1;
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        printf("\"%s\": %s\n", s, is_pal(s, n) ? "YES" : "NO");
    }
    return 0;
}

Input madam⏎ Nitin⏎ Never odd or even⏎:

"madam": YES
"Nitin": YES
"Never odd or even": YES

Input A man, a plan, a canal: Panama⏎ chai⏎ ⏎ (two spaces)⏎ ab⏎:

"A man, a plan, a canal: Panama": YES
"chai": NO
"": YES
"  ": YES
"ab": NO

Complexity: O(n) time (each pointer crosses the string at most once), O(1) space.

Complexity summary

Task Method Time Space
length sizeof(s) O(1), wrong (size of the array) O(1)
walk to '\0', strip '\n' O(n) O(1)
reverse swap every i with n-1-i O(n), unchanged string O(1)
two pointers, while (i < j) O(n), n/2 swaps O(1)
copy into a second array O(n) O(n)
palindrome raw two pointers O(n), wrong for case and spaces O(1)
skip with isalnum, compare tolower O(n) O(1)

strlen(s) is itself O(n): call it once and keep the result, don't put it in a loop condition.

Common mistakes (and the real results)

Mistake What you see Why Fix
printf("%d", sizeof(s)); warning: format '%d' expects argument of type 'int', but argument 2 has type 'long unsigned int', then length 100 sizeof is the array's size, and a size_t count to '\0'; print a size_t with %zu
count after fgets no error: length 6 for Priya fgets keeps the '\n' if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
for (i = 0; i < n; i++) swap i and n-1-i no error: the string is unchanged every pair is swapped twice while (i < j)
int j = n; no error: every line prints "" '\0' is moved to the front j = n - 1
char s[4] = "Priya"; warning: initializer-string for array of 'char' is too long no room for the text char s[] = "Priya"; (6 chars)
char s[5] = "Priya"; no warning in C, but no '\0': printing it is undefined behaviour the array has room for the letters only leave room for '\0'
tolower(s[i]) with a negative char no warning: undefined behaviour for non-ASCII text <ctype.h> needs unsigned char values or EOF tolower((unsigned char)s[i])
isalnum / tolower without #include <ctype.h> warning: implicit declaration of function the function isn't declared #include <ctype.h>

Here is the too-small array for real:

#include <stdio.h>
int main() {
    char a[5] = "Priya";
    char b[4] = "Priya";
    printf("%c %c\n", a[0], b[0]);
    return 0;
}

Compiler output:

main.c: In function 'main':
main.c:4:17: warning: initializer-string for array of 'char' is too long
    4 |     char b[4] = "Priya";
      |                 ^~~~~~~

Note there is no warning for a[5]: in C an array exactly as long as the letters is allowed, it just has no '\0'. Only a[0] and b[0] are printed here, which is safe; printing a with %s would not be.

Your turn: reverse the words (solution)

Problem. Reverse the order of the words in each line, in place: I love chai → chai love I. The letters inside each word stay the right way round.

Idea. Use Q2 twice. Reverse the whole line (chai becomes iahc evol I), then reverse each word back: a word ends at a space or at '\0'. Every character is swapped at most twice: O(n) time, O(1) space.

Show the solution
#include <stdio.h>
#include <string.h>

void reverse(char s[], int i, int j) {
    while (i < j) {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
        i++;
        j--;
    }
}

int main() {
    char s[100];
    while (fgets(s, sizeof s, stdin) != NULL) {
        int n = strlen(s);
        if (n > 0 && s[n - 1] == '\n') s[--n] = '\0';
        reverse(s, 0, n - 1);              /* 1. reverse the whole line */
        int start = 0;
        for (int k = 0; k <= n; k++) {     /* 2. reverse each word back */
            if (s[k] == ' ' || s[k] == '\0') {
                reverse(s, start, k - 1);
                start = k + 1;
            }
        }
        printf("\"%s\"\n", s);
    }
    return 0;
}

Input I love chai⏎ hello⏎ ⏎ New Delhi is big⏎:

"chai love I"
"hello"
""
"big is Delhi New"

Practice questions (with solutions)

1. String length with a pointer. Walk a pointer p to the '\0' and return p - s, the number of chars between them.

Solution
#include <stdio.h>

int length(const char *s) {
    const char *p = s;
    while (*p != '\0') p++;
    return p - s;
}

int main() {
    printf("%d %d %d\n", length("Priya"), length(""), length("New Delhi"));
    return 0;
}

Output:

5 0 9

2. Reverse a string with recursion. Swap the two ends, then reverse what is between them; stop when 0 or 1 character is left.

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

void rev(char s[], int i, int j) {
    if (i >= j) return;          /* base case: 0 or 1 character left */
    char t = s[i];
    s[i] = s[j];
    s[j] = t;
    rev(s, i + 1, j - 1);
}

int main() {
    char s[] = "Mumbai";
    rev(s, 0, (int)strlen(s) - 1);
    printf("%s\n", s);
    return 0;
}

Output:

iabmuM

Recursion uses O(n) stack space (n / 2 calls), unlike the loop.

3. Is a number a palindrome? (as a string) Turn the number into a string with snprintf (it returns the length written), then use the two-pointer check. A negative number is never a palindrome: -121 backwards is 121-.

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

int is_pal(const char s[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        if (s[i] != s[j]) return 0;
        i++;
        j--;
    }
    return 1;
}

int main() {
    int x;
    char s[20];
    while (scanf("%d", &x) == 1) {
        int n = snprintf(s, sizeof s, "%d", x);
        printf("%d: %s\n", x, is_pal(s, n) ? "YES" : "NO");
    }
    return 0;
}

Input 121 123 -121 7 1221:

121: YES
123: NO
-121: NO
7: YES
1221: YES

Quick quiz

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

int main() {
    char s[] = "chai";
    printf("%zu %zu\n", sizeof(s), strlen(s));
    return 0;
}

(A) 5 4 (B) 4 4 (C) 4 5 (D) 8 4

Answer

(A) 5 4. char s[] = "chai" makes the array exactly big enough: 4 letters + '\0' = 5 bytes. strlen counts the letters before '\0': 4.

Output:

5 4

Interview questions

  1. What is a string in C? A char array ending with the null terminator '\0'.
  2. sizeof(s) vs strlen(s)? sizeof is the size of the array in bytes, known at compile time; strlen counts the chars before '\0' at run time. For char s[100] = "Priya": 100 and 5.
  3. What does sizeof give for a pointer char *p? The size of the pointer (8 on 64-bit), not the string.
  4. Why does fgets leave a '\n', and how do you remove it? It stores the whole line including Enter; overwrite it with '\0' if the last char is '\n'.
  5. Reverse a string in place in O(n) time and O(1) space. Two pointers from both ends, swap, stop when i >= j.
  6. Check a palindrome ignoring case and non-letters. Two pointers, skip non-isalnum chars, compare with tolower.
  7. Why cast to unsigned char before tolower/isalnum? Negative values (other than EOF) are undefined behaviour.
  8. Why not call strlen in a loop condition? It is O(n) per call, so the loop can become O(n²).
  9. Reverse the words of a sentence in place. Reverse the whole string, then each word.

Glossary

Term Meaning Example
String A char array ending with '\0' "Priya" is 6 chars
char array An array whose elements are characters char s[100];
Null terminator '\0' The char with value 0 that marks the end of a string after the a in Priya
Length The number of chars before '\0' New Delhi → 9
strlen Library function in <string.h> that counts the chars before '\0' strlen("chai") = 4
sizeof The size of a variable or type in bytes, at compile time sizeof(char[100]) = 100
size_t Unsigned integer type for sizes, what sizeof and strlen return print with %zu
Unsigned An integer type with no negative values size_t, unsigned int
%zu The printf format for a size_t printf("%zu", sizeof s)
fgets Reads one line (with spaces and the '\n') into an array, or returns NULL at the end fgets(s, sizeof s, stdin)
NULL A pointer to nothing; fgets returns it at the end of the input while (fgets(...) != NULL)
const parameter A promise that the function won't change it int length(const char s[])
In place Changing the data inside the same array, with O(1) extra space reverse with swaps
Swap Exchange two values with a temporary t = a; a = b; b = t;
Two pointers Two indexes moving through the data, often from both ends i = 0, j = n - 1
Palindrome Reads the same forwards and backwards madam, Nitin
ASCII code The number that stores a character 'N' = 78, 'n' = 110
<ctype.h> Header with character tests and conversions tolower, isalnum, isspace
tolower Returns the small letter for a capital, any other char unchanged tolower('N') = 'n'
isalnum True for a letter or a digit (alphanumeric) isalnum(',') is false
isspace True for a space, tab or newline isspace(' ') is true
continue Jumps to the next check of the loop skip a space
Undefined behaviour (UB) The C standard makes no promise about the result tolower of a negative char
-Wall gcc option that turns on the common warnings caught %d for a size_t
Recursion A function calling itself on a smaller problem rev(s, i + 1, j - 1)
snprintf printf into a char array, at most its size; returns the length snprintf(s, sizeof s, "%d", x)

Summary

  • A string is a char array ending with '\0'; its length is the count before it. sizeof measures the whole array (and is a size_t: %zu).
  • fgets keeps the newline: strip it before counting or comparing.
  • Reverse in place with two pointers and while (i < j); looping to n reverses twice, and j = n moves the '\0' to the front.
  • Palindrome: skip what isn't isalnum, compare tolower (with unsigned char). All three are O(n) time, O(1) space.

Next episode: String questions II: count vowels, consonants, digits and words; toggle case; remove all spaces in place; fgets and the newline.