Reverse Words in a String - Solution & Explanation
Problem Statement
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 <= 104scontains English letters (upper-case and lower-case), digits, and spaces' '.- There is at least one word in
s.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
Approach Overview
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.
Approach 1: Split and Reverse Approach
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:
- Trimming the spaces at the beginning and end, and reducing multiple spaces in between words into a single space.
- Using
strtok()to split the string by spaces into separate words. - Building the result by reversing the order of insertion into the result string.
Complexity
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.
Approach 2: In-place Char Array Reversal
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.
Complexity
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 3: Two Pointers
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.
Approach 4: String Split
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.
Code
Python
Java
Go
TypeScript
Rust
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Reverse Words in a String | LeetCode 151 | C++, Java, Python • Knowledge Center • 213,355 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Words in a String easy or hard?
How to solve Reverse Words in a String in O(n)?
Reverse Words in a String Python or Java solution
What is the best approach for Reverse Words in a String?
Is Reverse Words in a String asked at Google/Amazon/Meta?
What data structure is used in Reverse Words in a String?
What is the time complexity of Reverse Words in a String?
Ready to solve this problem?
Practice Reverse Words in a String with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor