Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue" Output: "blue is sky the"
Example 2:
Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104s contains English letters (upper-case and lower-case), digits, and spaces ' '.s.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
Problem Overview: You are given a string that may contain leading, trailing, or multiple spaces between words. The task is to reverse the order of the words and return a clean string where words are separated by a single space. Characters inside each word stay in the same order; only the word order changes.
Approach 1: Split and Reverse Approach (O(n) time, O(n) space)
The most straightforward solution uses built-in string operations. First remove extra whitespace using a split operation that separates the string into words. This automatically ignores multiple spaces. Once you have the list of words, reverse the list and join it back into a single string using a single space as the delimiter.
The key idea is that splitting converts the problem from string manipulation to list manipulation. Reversing the list takes linear time, and joining reconstructs the final string. This approach is easy to write and highly readable, making it ideal for interviews where clarity matters. Most high-level languages such as Python, Java, and JavaScript provide efficient split() and join() utilities.
This method processes each character once during splitting and once during joining, giving O(n) time complexity and O(n) extra space for the list of words. The approach heavily relies on basic string operations.
Approach 2: In-place Char Array Reversal (O(n) time, O(1) extra space)
This approach avoids allocating additional structures and works directly on a mutable character array. The algorithm has three main steps. First trim extra spaces so the string contains only single spaces between words. Second reverse the entire character array. Third iterate through the array and reverse each word individually using two pointers.
Reversing the whole string moves words into the correct order but also reverses characters inside each word. The second pass fixes this by reversing each word segment back to normal. Two pointers track the start and end of each word and perform in-place swaps.
This technique runs in O(n) time since each character is visited a constant number of times. Extra space is O(1) because the operations modify the array directly. The algorithm relies heavily on pointer movement and boundary detection, a classic pattern in two pointers problems.
Recommended for interviews: Start with the split-and-reverse explanation because it clearly demonstrates the problem logic. Then mention the in-place reversal method as the optimized approach when memory usage matters. Interviewers often expect candidates to recognize both: the simple string-processing solution and the pointer-based optimization.
This approach involves splitting the original string into individual words using space as a delimiter, reversing the list of words, and then joining them back together with a single space.
The C solution involves:
strtok() to split the string by spaces into separate words.Time Complexity: O(N), where N is the length of the string, as we process each character once.
Space Complexity: O(N), additional space for intermediate and result storage.
This optimized approach manipulates the string in place by using a character array. We'll first reverse the entire string, and then reverse each word to return them to their correct order.
This C solution reverses the string in place using a helper function reverseCharArray. It then iterates over the string, reversing individual words and reconstructing the string without additional leading or trailing spaces.
Time Complexity: O(N), where N is the number of characters in the string.
Space Complexity: O(1), as the operation is done in-place without extra space.
We can use two pointers i and j to find each word, add it to the result list, then reverse the result list, and finally concatenate it into a string.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string.
We can use the built-in string split function to split the string into a list of words by spaces, then reverse the list, and finally concatenate it into a string.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string.
Python
Java
Go
TypeScript
Rust
| Approach | Complexity |
|---|---|
| Split and Reverse Approach | Time Complexity: O(N), where N is the length of the string, as we process each character once. Space Complexity: O(N), additional space for intermediate and result storage. |
| In-place Char Array Reversal | Time Complexity: O(N), where N is the number of characters in the string. Space Complexity: O(1), as the operation is done in-place without extra space. |
| Two Pointers | — |
| String Split | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split and Reverse Approach | O(n) | O(n) | Best for readability and quick implementation using built-in string utilities. |
| In-place Char Array Reversal | O(n) | O(1) | Preferred when minimizing extra memory or when working with mutable character arrays. |
Reverse Words in a String | LeetCode 151 | C++, Java, Python • Knowledge Center • 211,943 views views
Watch 9 more video solutions →Practice Reverse Words in a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor