</>EmbeddedInterview

How do you reverse the order of words in a string?

MediumArrays & Strings (Coding Round)

Short answer: Reverse the whole string, then reverse each word in place. "hello world" → "dlrow olleh" → "world hello". O(n) time, O(1) extra space.

#include <string.h>

static void reverse_range(char *s, size_t lo, size_t hi)   /* inclusive */
{
    while (lo < hi) {
        char t = s[lo]; s[lo] = s[hi]; s[hi] = t;
        lo++; hi--;
    }
}

void reverse_words(char *s)
{
    size_t len = strlen(s);
    if (len == 0) return;
    reverse_range(s, 0, len - 1);           /* step 1: whole string */

    size_t start = 0;
    for (size_t i = 0; i <= len; i++) {     /* <= len: also handle the last word */
        if (s[i] == ' ' || s[i] == '\0') {
            if (i > start)
                reverse_range(s, start, i - 1);   /* step 2: each word */
            start = i + 1;
        }
    }
}
/* "hello world" -> "world hello" */

Dry run: "hello world" → whole reverse → "dlrow olleh" → reverse "dlrow" → "world", reverse "olleh" → "hello" → "world hello".

Details that catch people out

  • The last word is not followed by a space. Looping to i <= len and treating '\0' as a separator handles it.
  • Consecutive spaces: if (i > start) skips empty "words", so "a b" does not call reverse with hi < lo. With size_t, i - 1 when i == 0 would wrap to a huge number.
  • Leading, trailing or multiple spaces that must be collapsed to one: do an extra compaction pass (two pointers, copy a single space between words).

Why reverse twice? Reversing the whole string puts the words in the right order but each word is backwards; the second pass fixes each word. It avoids a second buffer, which matters on a small MCU.

Alternative with extra memory: split into words (strtok or manual), then print them in reverse. Note that strtok modifies the string and is not reentrant (strtok_r is).