Reverse Words in a String

Difficulty: Medium

Problem

You are given a string s made up of words separated by spaces, where a word is any run of non-space characters. Produce a new string with the words in the opposite order, joined by exactly one space each. The input may start or end with spaces and may have several spaces between words, but the result must not have any leading, trailing, or repeated spaces.

Example

Input: s = "  moon  over   water "
Output: "water over moon"
Explanation: Splitting on the spaces gives the words "moon", "over" and "water". Listed in reverse and joined by single spaces: "water over moon".

Brute-force approach

Split the string by spaces, filter out empty entries, reverse the list of words, and join with a single space.

Steps

  1. Split the string by whitespace
  2. Filter out empty strings
  3. Reverse the word list
  4. Join with single space

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for the word list
  • Relies on built-in split, interviewers may ask for in-place
  • Some languages create intermediate string copies during split

Optimal approach

Key insight: Reversing the entire string puts words in the right order but with reversed characters. Reversing each word individually fixes the characters.

For an in-place approach: (1) reverse the entire string, (2) reverse each individual word, (3) clean up extra spaces. This avoids the word list allocation.

Steps

  1. Trim leading/trailing spaces, collapse multiple spaces
  2. Reverse the entire character array
  3. Iterate through, reverse each word individually
  4. Return the result string

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function reverseWords(s):
    words = split s by whitespace (remove empty entries)
    reverse the words array
    return join words with single space

Hints

  • Split on whitespace to handle multiple spaces
  • Filter out empty strings from the split result
  • Reverse the resulting word array and join with single space

Complexity questions

What is the time complexity of the split + reverse + join approach?

O(n). Split is O(n), filter is O(w), reverse is O(w), join is O(n). Total: O(n).

What is the space complexity of the in-place (reverse all + reverse each) approach?

O(1) in mutable-string languages. In C/C++ with mutable char arrays, only pointer variables are used. In Python/Java (immutable strings), you still need O(n) for the char array.

Why does reversing the entire string and then reversing each word produce the correct result?

The first reverse puts words in correct order (reversed chars), the second fixes chars within each word. Full reverse swaps word positions. Per-word reverse restores character order within each word.

Check your understanding of Reverse Words in a String

Given s = " hello world ", what should the output be?

"world hello". Reverse word order: "hello" then "world" → "world hello". No extra spaces.

How should multiple spaces between words be handled?

Replace with exactly one space. All multiple spaces are collapsed to a single space in the output.

Given s = "a", what is the output?

"a". A single word reversed is just itself: "a".

Related problems

Keep practising