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: Given a string that may contain leading, trailing, or multiple spaces between words, return a new string with the words in reverse order. Words must appear in reverse sequence while extra spaces are removed so only a single space separates words.
Approach 1: Split and Reverse Approach (O(n) time, O(n) space)
The most straightforward method uses built-in string operations. First remove leading and trailing spaces, then split the string into words using whitespace as the delimiter. This produces an array of tokens representing each word. Reverse that array and join the elements with a single space using join(). The key insight is that string libraries already handle tokenization efficiently, so reversing the resulting list becomes trivial.
This approach performs a single pass over the string during splitting and another pass when joining, giving O(n) time complexity. The array of words requires O(n) additional space. It is easy to implement and highly readable, making it common in high-level languages like Python, JavaScript, and Java.
Problems like this appear frequently in string manipulation interviews where clarity matters more than micro-optimizations. If the language provides reliable split and join utilities, this solution is often acceptable.
Approach 2: In-place Char Array Reversal (O(n) time, O(1) extra space)
This approach avoids allocating an array of words by manipulating characters directly. Convert the string into a mutable character array. First reverse the entire array so the word order is flipped. Then iterate through the array and reverse each word individually to restore its character order.
While scanning, use two pointers to detect word boundaries. Skip extra spaces, copy valid characters forward, and ensure only a single space separates words. This step effectively trims leading, trailing, and duplicate spaces while rebuilding the string in place.
The algorithm performs a few linear scans and constant-time swaps, giving O(n) time complexity with O(1) extra space (excluding the mutable array representation). This technique relies heavily on pointer movement and substring reversal patterns commonly used in two pointers problems.
This approach appears more frequently in lower-level languages such as C or C++, where minimizing extra memory is valuable and string operations are often implemented manually.
Recommended for interviews: Start by describing the split-and-reverse solution because it demonstrates clear understanding and solves the problem quickly in O(n) time. Then mention the in-place reversal technique as the optimized version with O(1) extra space. Interviewers usually expect the candidate to recognize both patterns: high-level string processing and pointer-based in-place manipulation.
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.C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split and Reverse | O(n) | O(n) | Best for readability and quick implementation using built-in string utilities |
| In-place Char Array Reversal | O(n) | O(1) | When memory usage matters or interviewers want pointer-based manipulation |
Reverse Words in a String | LeetCode 151 | C++, Java, Python • Knowledge Center • 201,648 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