151. Reverse Words in a String - Detailed Explanation

Problem statement

Description:
Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The input string may contain leading or trailing spaces, and multiple spaces between words. The returned string should have the words in reverse order and be trimmed so that there is only a single space between words.

Examples:

• Example 1:

  • Input: "the sky is blue"
  • Output: "blue is sky the"
  • Explanation: The words are reversed.

• Example 2:

  • Input: " hello world "
  • Output: "world hello"
  • Explanation: The leading and trailing spaces are removed, and only a single space separates the words in the reversed string.

• Example 3:

  • Input: "a good example"
  • Output: "example good a"
  • Explanation: Multiple spaces between words are reduced to a single space in the final output.

Constraints:

• The input string may contain extra spaces.
• Words are separated by one or more spaces.
• The output should have no leading or trailing spaces, and words must be separated by a single space.

Hints before you begin

• Hint 1:
  Think about how to separate the string into words. A built-in split on whitespace usually collapses runs of spaces and discards the leading and trailing ones for you.

• Hint 2:
  Once you hold the list of words, decide how to reverse its order without copying it twice.

• Hint 3:
  Join the reversed list back into a single string, using one space as the delimiter.

Two interviewers can ask this question for two different skills. One wants to see you call the library function and move on. The other wants the in-place version, which is an instance of the Two Pointers pattern: you place one index at each end of a range and walk them toward each other, swapping as they go. That pattern reverses a whole string, reverses each word inside it, and also drives the space-compaction step, so a single idea covers all three. It sits on every short list of recurring coding interview patterns for exactly that reason.

Approaches to solve the problem

1. Brute force approach using split and reverse

Idea:

• Step 1: Split the input string into words. Most languages offer built-in functions that split a string on whitespace, automatically handling multiple spaces.
• Step 2: Reverse the list of words.
• Step 3: Join the reversed list using a single space.

Benefits:

• The approach is short, and the built-in functions carry most of the work.
• Trimming and runs of spaces are handled for you.

Drawbacks:

• The solution allocates extra space for the list of words.

2. In-place reversal (advanced approach)

Idea:

• Step 1: Remove extra spaces by trimming and compressing multiple spaces into one.
• Step 2: Reverse the entire string.
• Step 3: Reverse each word in the reversed string to restore the correct word order.

Take "the sky is blue". Reversing all of it yields "eulb si yks eht", which already has the words in the order you want, each one spelled backward. Reversing every word in place then repairs the letters and leaves "blue is sky the". Each reversal is the same two-pointer loop, called once on the full range and then once per word.

Benefits:

• Languages with mutable strings, or a character array stand-in, can run all three steps inside the input buffer and keep the extra space to a handful of indices.

Drawbacks:

• The in-place version takes more code, and the word boundaries invite off-by-one errors.

For most interview settings, the split-reverse-join method is acceptable and easier to understand. Name the in-place variant anyway, state its space advantage, and write it if the interviewer asks for O(1) extra space.

Code implementations

Python code implementation