Watch 10 video solutions for Reverse Words in a String, a medium level problem involving Two Pointers, String. This walkthrough by Knowledge Center has 201,648 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |