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
- Trim
s, then split it on runs of whitespace so that consecutive spaces never produce empty tokens - Reverse the array of words in place
- Join the words with a single space and return the result
Visualization and Code
Loading animation...
- 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) inow sits on the last character of a word. Set a second pointerj = iand movejleft whiles[j]is not a space- The word is
s[j+1 ... i] - If the result is not empty, append a space before the word
- Append the word to the result
- Set
i = jso the next iteration continues from just before this word - Return the result
Visualization and Code
Loading animation...
- 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
Visualization and Code
Loading animation...
- 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.