Reverse Words in a String
Understanding the Problem
This looks like a "split and reverse" problem, and in many languages it is close to that. Two details make it harder than it appears.
First, the input can have leading spaces, trailing spaces, and multiple spaces between words. The output must have exactly one space between words and no extra spaces at either end. Reversing the entire string is not enough, because the spaces would land in the wrong places.
Second, the follow-up asks whether you can solve it in O(1) extra space when the string is mutable. The in-place idea is to reverse the entire string first, which puts the words in the correct order but spells each word backwards, then reverse each word individually to restore it. The sections below build up to this.
Key Constraints:
1 <= s.length <= 10^4→ The string is small enough that an O(n) scan is fast, and large enough that we should avoid repeatedly building intermediate strings inside a loop, which can degrade to O(n^2).scontains letters, digits, and spaces → A word is any contiguous run of non-space characters. There are no other delimiters to handle.- There is at least one word → The result is never empty, so we do not need a special empty-output case.
Approach 1: Split and Reverse (Built-in Functions)
Intuition
Use the language's built-in string operations. Split the string on spaces to get the individual words, drop any empty strings produced by consecutive spaces, reverse the list of words, and join them back with a single space.
This is a valid solution. The follow-up is usually to do it without split and join, which Approach 2 covers.
Algorithm
- Split the string
sby spaces to get an array of tokens - Filter out any empty strings from the array (caused by multiple consecutive spaces)
- Reverse the array of words
- Join the words with a single space and return the result
Example Walkthrough
Code
- Time Complexity: O(n). Splitting the string takes O(n), reversing the word list takes O(k) where k is the number of words, and joining takes O(n). Overall O(n).
- Space Complexity: O(n). We store all the words in a separate array, which in the worst case holds all n characters.
This approach relies on built-in split and join. The next approach extracts words by scanning the string directly, without any split helper.
Approach 2: Two Pointers (Reverse Traversal)
Intuition
Scan the string from right to left and extract words by index. Traversing backwards visits the words in reverse order, which is the order we want them in the output, so no separate reversal step is needed.
Two pointers mark the boundaries of each word. Start at the end of the string, skip trailing spaces, then move left until the start of the word. The slice between those positions is one word. Append it to the result and repeat until the whole string is processed.
Algorithm
- Initialize an empty result (StringBuilder or equivalent) and set pointer
ito the last index of the string - While
i >= 0: - Skip spaces by decrementing
iwhiles[i]is a space - If
i < 0, break (we've processed everything) - Set
end = i(this is the last character of the current word) - Move
ileft whiles[i]is not a space andi >= 0to find the start of the word - The word is
s[i+1 ... end] - If the result is not empty, append a space before the word
- Append the word to the result
- Return the result
Example Walkthrough
Take s = " hello world " (indices 0 to 14, with two leading and two trailing spaces). The pointer i starts at 14.
Code
- Time Complexity: O(n). We scan through the string once from right to left, doing O(1) work per character.
- Space Complexity: O(n). We build a new result string/list that holds all the characters. In languages with immutable strings (Java, Python, C#), this is unavoidable.
Both approaches so far use O(n) extra space for the result. The next approach rearranges characters within the input itself, reversing the entire string first and then reversing each word.
Approach 3: Reverse Entire String, Then Reverse Each Word
Intuition
This answers the follow-up: "Can you do it in O(1) extra space if the string is mutable?"
Consider the string "the sky is blue":
- Reverse the entire string:
"eulb si yks eht" - The words are now in the correct order ("eulb" was "blue", "si" was "is", and so on), but each word is spelled backwards.
- Reverse each individual word:
"blue is sky the"
Two passes reverse the word order while keeping each word intact. Why this works: reversing the whole string maps the word at positions [a, b] to positions [n-1-b, n-1-a], which preserves the relative order of words back-to-front, and reversing a contiguous block twice (once as part of the whole, once on its own) returns it to its original spelling.
Extra spaces still need handling. After the full reversal, runs of spaces remain, and the second pass uses a write pointer to compact them so exactly one space separates words and no spaces remain at the ends.
Algorithm
- Convert the string to a mutable character array
- Reverse the entire character array
- Use a write pointer to process each word:
- Skip leading spaces
- If the write pointer is not at position 0, write a single space (word separator)
- Copy the word characters to the write position
- Reverse the word that was just written (to un-reverse it)
- Return the substring from index 0 to the write pointer
Example Walkthrough
Take s = "a good example" (16 characters, with three spaces between "good" and "example"). The expected answer is "example good a".
Code
- Time Complexity: O(n). We make two passes through the string: one to reverse the whole thing, and one to reverse each word and compact spaces. Each pass is O(n).
- Space Complexity: O(1) auxiliary in C++, where we modify the string in place and use only a constant number of pointer variables. In the languages with immutable strings (Java, Python, C#, Go, JavaScript, TypeScript), we first copy the input into a mutable character array, so the space is O(n) there. The algorithm itself never allocates beyond that single buffer.