Reverse Words in a String
MedPrompt
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?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach leverages the built-in functions provided by the programming language, such as trim, split, and join, along with collection reversal utilities. It's often the most concise and readable solution for this problem.
Algorithm
- Remove leading and trailing whitespace from the input string
susingtrim(). - Split the trimmed string by one or more spaces (
"\\s+") to get an array of words. - Create a
Listfrom the array of words to use theCollections.reverse()utility. - Reverse the order of elements in the list.
- Join the words in the reversed list with a single space separator using
String.join()to form the final string.
Walkthrough
The simplest way to solve this problem is by using high-level, built-in string and collection manipulation functions. The process is straightforward:
- Trim: The input string
scan have leading or trailing spaces.s.trim()removes these. - Split: The trimmed string is then split into words. The key is to use a regular expression like
"\\s+"as the delimiter, which handles cases with multiple spaces between words, treating them as a single separator. - Reverse: The resulting array of words is converted to a list, which is then reversed using
Collections.reverse(). - Join: Finally,
String.join(" ", words)concatenates the elements of the reversed list into a single string, with each word separated by a single space.
import java.util.Arrays;import java.util.Collections; class Solution { public String reverseWords(String s) { // 1. Trim leading and trailing spaces String trimmedStr = s.trim(); // 2. Split by one or more spaces String[] words = trimmedStr.split("\\s+"); // 3. Reverse the array of words Collections.reverse(Arrays.asList(words)); // 4. Join the words with a single space return String.join(" ", words); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Very simple and concise, leading to highly readable code.
Leverages optimized and well-tested library functions, reducing the chance of bugs.
Cons
Creates intermediate data structures (an array of strings and a list), which can consume significant memory, making it O(N) in space complexity.
May not be allowed in interviews that restrict the use of certain built-in functions to test fundamental algorithm knowledge.
This approach avoids using the split function by manually iterating through the string from end to beginning. It identifies words one by one and appends them to a StringBuilder to construct the reversed string.
Algorithm
- Initialize an empty
StringBuilderto store the result. - Iterate through the input string
sfrom right to left using an indexi. - Skip any trailing spaces by decrementing
i. - When a non-space character is found, it marks the end of a word. Use another pointer
jto find the start of this word by moving leftwards fromi. - Once the word is identified (from
j+1toi+1), append it to theStringBuilder. - After appending a word, append a single space to the
StringBuilderbefore searching for the next word. - Continue this process until the beginning of the string is reached.
- Finally, remove the last appended space from the
StringBuilderand return the result.
Walkthrough
Instead of splitting the string into an array, we can build the reversed string directly. By scanning the string from right to left, we encounter the words in the order we need them for the final result (last word first, etc.).
We use a pointer i to scan the string from the end. We first skip any spaces to find the end of a word. Then, we find the beginning of that same word. Once we have the word's boundaries, we extract it using substring and append it to a StringBuilder. We then append a space and continue scanning leftwards for the next word. This method avoids creating an intermediate array of all words at once.
class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(); int i = s.length() - 1; while (i >= 0) { // Skip trailing spaces of a word while (i >= 0 && s.charAt(i) == ' ') { i--; } if (i < 0) break; // Find the start of the word int j = i; while (j >= 0 && s.charAt(j) != ' ') { j--; } // Append the word. If sb is not empty, add a space first. if (sb.length() > 0) { sb.append(' '); } // The word is from j+1 to i+1 sb.append(s.substring(j + 1, i + 1)); // Move i to the position before the current word i = j; } return sb.toString(); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
More memory-efficient than the split-based approach as it avoids creating an intermediate array of strings.
Demonstrates a good understanding of string manipulation and pointer-based logic.
Cons
The logic is more complex and requires careful pointer management compared to using built-in functions.
Still requires O(N) extra space for the
StringBuilder, so it's not the most memory-efficient solution.
This is the most optimal approach in terms of space complexity, addressing the follow-up question. It modifies the string (or a character array representation) in-place. The core idea is a three-pass algorithm: first, clean up all extra spaces; second, reverse the entire string; and third, reverse each word individually.
Algorithm
- (Clean Spaces): Convert the string to a
char[]. Use a two-pointer approach (read and write pointers) to create a compact sequence of words at the beginning of the array, separated by single spaces. This removes all leading, trailing, and extra intermediate spaces. Keep track of the new, shorter length. - (Reverse All): Reverse the entire cleaned-up portion of the character array. After this step, the words are in the correct order, but each word itself is spelled backward.
- (Reverse Words): Iterate through the array again. Identify the boundaries of each word (sequences of non-space characters) and reverse each word in-place.
- (Final String): Create a new string from the modified character array, using the new length calculated in the first step.
Walkthrough
To achieve O(1) extra space, we must perform the reversal in-place on a mutable data structure, like a character array in Java. The algorithm consists of three main steps:
- Clean Spaces: This pass normalizes the string. We use a write pointer
iand a read pointerj. We iterate through the array, copying words to the front and ensuring only a single space is placed between them. This effectively removes all unwanted spaces and gives us a new, shorter effective length for the string. - Reverse the Entire Array: We reverse all characters in the cleaned-up portion of the array. For example,
"the sky is blue"becomes"eulb si yks eht". - Reverse Each Word: We iterate through the array one last time. We find the start and end of each word (now separated by single spaces) and reverse them.
"eulb"becomes"blue","si"becomes"is", and so on. This restores the words to their correct spelling while keeping their reversed order.
class Solution { public String reverseWords(String s) { if (s == null) return null; char[] a = s.toCharArray(); int n = a.length; // Step 1: Reverse the entire string reverse(a, 0, n - 1); // Step 2: Reverse each word reverseWords(a, n); // Step 3: Clean up spaces return cleanSpaces(a, n); } // Helper to reverse a sub-array private void reverse(char[] a, int i, int j) { while (i < j) { char temp = a[i]; a[i++] = a[j]; a[j--] = temp; } } // Helper to reverse words in the array private void reverseWords(char[] a, int n) { int i = 0, j = 0; while (i < n) { // Skip spaces to find the start of a word while (i < n && a[i] == ' ') i++; j = i; // Find the end of the word while (j < n && a[j] != ' ') j++; // Reverse the word reverse(a, i, j - 1); i = j; } } // Helper to clean up spaces private String cleanSpaces(char[] a, int n) { int i = 0, j = 0; while (j < n) { // Skip spaces while (j < n && a[j] == ' ') j++; // Copy word while (j < n && a[j] != ' ') a[i++] = a[j++]; // Skip spaces while (j < n && a[j] == ' ') j++; // Add one space after a word if it's not the end if (j < n) a[i++] = ' '; } return new String(a).substring(0, i); }}Note: The provided code implements a slightly different but equally valid 3-step in-place logic (Reverse All -> Reverse Words -> Clean Spaces) which is also a common way to solve it.
Complexity
Time
O(N)
Space
O(1) (for the algorithm itself)
Trade-offs
Pros
Extremely space-efficient, using O(1) extra space (not counting the initial character array).
An excellent solution for environments with strict memory constraints.
Demonstrates a deep understanding of array manipulation and in-place algorithms, which is highly valued in technical interviews.
Cons
The algorithm is significantly more complex to understand and implement correctly.
In languages with immutable strings like Java or Python, an initial O(N) space cost is unavoidable to create a mutable character array. The O(1) space complexity refers to the extra space used by the algorithm itself.
The process modifies the character array, which might not be desirable in all situations.
Solutions
Solution
public class Solution { public string ReverseWords(string s) { return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse()); }}class Solution {public String reverseWords(String s) { List<String> words = Arrays.asList(s.trim().split("\\s+")); Collections.reverse(words); return String.join(" ", words); }}class Solution {public: string reverseWords(string s) { int i = 0; int j = 0; int n = s.size(); while (i < n) { while (i < n && s[i] == ' ') { ++i; } if (i < n) { if (j != 0) { s[j++] = ' '; } int k = i; while (k < n && s[k] != ' ') { s[j++] = s[k++]; } reverse(s.begin() + j - (k - i), s.begin() + j); i = k; } } s.erase(s.begin() + j, s.end()); reverse(s.begin(), s.end()); return s; }};class Solution: def reverseWords(self, s: str) -> str: words = s . strip(). split() return ' ' . join(words[:: - 1]) # class Solution : # O(1) space complexity def reverseWords ( self , s : str ) -> str : # Remove leading and trailing spaces s = s . strip () # Reverse the entire string s = self . reverseString ( s , 0 , len ( s ) - 1 ) # Reverse each word in the string start = 0 end = 0 while end < len ( s ): if s [ end ] == ' ' : s = self . reverseString ( s , start , end - 1 ) start = end + 1 end += 1 # Reverse the last word s = self . reverseString ( s , start , end - 1 ) return s def reverseString ( self , s : str , start : int , end : int ) -> str : # Convert the string to a list of characters chars = list ( s ) # Reverse the substring while start < end : chars [ start ], chars [ end ] = chars [ end ], chars [ start ] start += 1 end -= 1 # Convert the list of characters back to a string return '' . join ( chars ) ############ class Solution ( object ): def reverseWords ( self , s ): """ :type s: str :rtype: str """ return " " . join ( s . split ()[:: - 1 ])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.