Reverse Words in a String solution and explanation
Google
Infosys
IBM
Cisco
9 more videos on this problem
Reverse Words in a String | LeetCode 151 | C++, Java, PythonKnowledge Center · 13:58 · 213K views
Reverse words in a string | Leetcode problem 151 | Top 150 interview question seriesTechnosage · 6:08 · 94K views
Reverse Words in a String (Amazon, Microsoft, MentorGraphics, MakeMyTrip) : Explanation➕Live CodingcodestorywithMIK · 22:53 · 51K views
REVERSE WORDS IN A STRING | LEETCODE 151 | PYTHON SOLUTIONCracking FAANG · 8:21 · 19K views
Reverse Words in a String - LeetCode 151 - Python #leetcode75Deepti Talesra · 4:16 · 7K views
Reverse Words In A String - 151. LeetCode - JavaTeddy Smith · 6:16 · 1K views
Leetcode 151 - Reverse Words in a StringData Engineering Studies · 8:04 · 577 views
LeetCode 151. Reverse Words in a String with Microsoft Engineerandreyka26_se · 12:10 · 471 views
151. Reverse words in a string | LeetcodeAbIn · 8:36 · 345 views
LeetCode 151: Reverse Words in a String | C# Solution | String ManipulationCode Scribbler · 3:24 · 182 views
The problem
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.
def reverseWords(s: str) -> str:
words = s.split()
return ' '.join(reversed(words))
input_str = " hello world "
output_str = reverseWords(input_str)
print(output_str)import java.util.ArrayList;
import java.util.List;
public class Solution {
public static String reverseWords(String s) {
String[] words = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i]);
if (i != 0) sb.append(" ");
}
return sb.toString();
}
public static void main(String[] args) {
String input = " hello world ";
String output = reverseWords(input);
System.out.println(output);
}
}#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
std::string reverseWords(std::string s) {
std::stringstream ss(s);
std::string word;
std::vector<std::string> words;
while (ss >> word) {
words.push_back(word);
}
std::reverse(words.begin(), words.end());
std::string result;
for (const std::string& w : words) {
if (!result.empty()) {
result += " ";
}
result += w;
}
return result;
}
int main() {
std::string input = " hello world ";
std::string output = reverseWords(input);
std::cout << output << std::endl;
return 0;
}function reverseWords(s) {
return s.trim().split(/\s+/).reverse().join(' ');
}
let input = " hello world ";
let output = reverseWords(input);
console.log(output);#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* reverseWords(char *s) {
// calculate length
int len = strlen(s), start = 0, wordCount = 0;
char *temp = malloc(len + 1);
char *result = malloc(len + 1);
temp[0] = '\0'; result[0] = '\0';
// trim leading and trailing spaces
while (s[start] == ' ') start++;
int end = len - 1;
while (s[end] == ' ') end--;
for (int i = start; i <= end; i++) {
if (s[i] != ' ') {
strncat(temp, &s[i], 1);
} else if (s[i] == ' ' && (i == start || s[i - 1] != ' ')) {
strcat(temp, " ");
}
}
char *token = strtok(temp, " ");
while (token != NULL) {
if (wordCount > 0) {
memmove(result + strlen(token) + 1, result, strlen(result) + 1);
memcpy(result, " ", 1);
}
memmove(result + strlen(token), result, strlen(result) + 1);
memcpy(result, token, strlen(token));
token = strtok(NULL, " ");
wordCount++;
}
free(temp);
return result;
}
int main() {
char input[] = " hello world ";
char* output = reverseWords(input);
printf("%s\n", output);
free(output);
return 0;
}using System;
public class Solution {
public static string ReverseWords(string s) {
string[] words = s.Trim().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
Array.Reverse(words);
return string.Join(" ", words);
}
public static void Main() {
string input = " hello world ";
string output = ReverseWords(input);
Console.WriteLine(output);
}
}The Python solution is concise with split() and reversed() to obtain reversed words and join them together with a space.
Time Complexity: O(N), where N is the number of characters in the string.
Space Complexity: O(N), due to storage needed for the split words.
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.
def reverseWords(s: str) -> str:
chars = list(s.strip())[::-1]
n = len(chars)
def reverse(start, end):
while start < end:
chars[start], chars[end] = chars[end], chars[start]
start, end = start + 1, end - 1
start = 0
while start < n:
if chars[start] == ' ':
start += 1
continue
end = start
while end < n and chars[end] != ' ':
end += 1
reverse(start, end - 1)
start = end + 1
return ' '.join(''.join(chars).split())
input_str = " hello world "
output_str = reverseWords(input_str)
print(output_str)public class Solution {
public static String reverseWords(String s) {
char[] chars = s.toCharArray();
int n = chars.length;
reverse(chars, 0, n - 1);
int start = 0, end = 0, index = 0;
while (index < n) {
while (index < n && chars[index] == ' ') index++;
start = index;
while (index < n && chars[index] != ' ') index++;
end = index - 1;
reverse(chars, start, end);
if (end >= start) start = ++end;
if (start < n && chars[start] != ' ') chars[++end] = ' ';
}
return new String(chars, 0, start);
}
public static void reverse(char[] array, int start, int end) {
while (start < end) {
char temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
}
public static void main(String[] args) {
String input = " hello world ";
System.out.println(reverseWords(input));
}
}#include <iostream>
#include <algorithm>
void reverseWord(char* s, int start, int end) {
while (start < end) {
std::swap(s[start++], s[end--]);
}
}
std::string reverseWords(std::string s) {
// Reverse the whole string
std::reverse(s.begin(), s.end());
int n = s.length(), wordStart = 0, resultIndex = 0;
while (wordStart < n) {
while (wordStart < n && s[wordStart] == ' ') wordStart++;
if (wordStart == n) break;
int wordEnd = wordStart;
while (wordEnd < n && s[wordEnd] != ' ') wordEnd++;
std::reverse(s.begin() + wordStart, s.begin() + wordEnd);
if (resultIndex > 0) s[resultIndex++] = ' ';
while (wordStart < wordEnd) s[resultIndex++] = s[wordStart++];
}
s.resize(resultIndex);
return s;
}
int main() {
std::string input = " hello world ";
std::cout << reverseWords(input) << std::endl;
return 0;
}function reverseWords(s) {
let chars = s.trim().split('');
const reverse = (start, end) => {
while (start < end) {
[chars[start], chars[end]] = [chars[end], chars[start]];
start++;
end--;
}
};
const n = chars.length;
reverse(0, n - 1);
let wordStart = 0, resultIndex = 0;
for (let i = 0; i < n; i++) {
if (chars[i] === ' ') continue;
wordStart = i;
while (i < n && chars[i] !== ' ') i++;
reverse(wordStart, i - 1);
resultIndex = wordStart;
while (wordStart < i) chars[resultIndex++] = chars[wordStart++];
if (resultIndex < n) chars[resultIndex++] = ' ';
}
return chars.join('').trim();
}
let input = " hello world ";
let output = reverseWords(input);
console.log(output);#include <stdio.h>
#include <string.h>
#include <stdbool.h>
void reverseCharArray(char* arr, int start, int end) {
while (start < end) {
char temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
char* reverseWords(char* s) {
int n = strlen(s);
// Reverse the entire string
reverseCharArray(s, 0, n - 1);
// Trim spaces and reverse each word within the string
int resultIndex = 0;
for (int i = 0; i < n; ) {
while (i < n && s[i] == ' ') i++;
int start = resultIndex;
while (i < n && s[i] != ' ') {
s[resultIndex++] = s[i++];
}
reverseCharArray(s, start, resultIndex - 1);
if (resultIndex < n) s[resultIndex++] = ' ';
}
// Remove any trailing space
if (resultIndex > 0 && s[resultIndex - 1] == ' ') resultIndex--;
s[resultIndex] = '\0';
return s;
}
int main() {
char input[] = " hello world ";
printf("%s\n", reverseWords(input));
return 0;
}using System;
using System.Text;
public class Solution {
public static string ReverseWords(string s) {
char[] chars = s.Trim().ToCharArray();
int n = chars.Length;
void Reverse(int start, int end) {
while (start < end) {
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;
end--;
}
}
Reverse(0, n - 1);
int rightIndex = 0;
for (int i = 0; i < n; ++i) {
if (chars[i] == ' ') continue;
int start = i;
while (i < n && chars[i] != ' ') i++;
Reverse(start, i - 1);
while (start < i) chars[rightIndex++] = chars[start++];
if (rightIndex < n) chars[rightIndex++] = ' ';
}
return new String(chars, 0, rightIndex == 0 ? 0 : rightIndex - 1);
}
public static void Main() {
string input = " hello world ";
string output = ReverseWords(input);
Console.WriteLine(output);
}
}The Python solution focuses on reversing the entire string initially, followed by reversing every word back to its correct order. The final result is constructed by joining words effectively.
Time Complexity: O(N), processing each character multiple times.
Space Complexity: O(1), in-place within the character array.
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.
function reverseWords(s: string): string {
const words: string[] = [];
const n = s.length;
let i = 0;
while (i < n) {
while (i < n && s[i] === ' ') {
i++;
}
if (i < n) {
let j = i;
while (j < n && s[j] !== ' ') {
j++;
}
words.push(s.slice(i, j));
i = j;
}
}
return words.reverse().join(' ');
}func reverseWords(s string) string {
words := []string{}
i, n := 0, len(s)
for i < n {
for i < n && s[i] == ' ' {
i++
}
if i < n {
j := i
t := []byte{}
for j < n && s[j] != ' ' {
t = append(t, s[j])
j++
}
words = append(words, string(t))
i = j
}
}
for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
words[i], words[j] = words[j], words[i]
}
return strings.Join(words, " ")
}impl Solution {
pub fn reverse_words(s: String) -> String {
let mut words = Vec::new();
let s: Vec<char> = s.chars().collect();
let mut i = 0;
let n = s.len();
while i < n {
while i < n && s[i] == ' ' {
i += 1;
}
if i < n {
let mut j = i;
while j < n && s[j] != ' ' {
j += 1;
}
words.push(s[i..j].iter().collect::<String>());
i = j;
}
}
words.reverse();
words.join(" ")
}
}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.
function reverseWords(s: string): string {
return s.trim().split(/\s+/).reverse().join(' ');
}func reverseWords(s string) string {
words := strings.Fields(s)
for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
words[i], words[j] = words[j], words[i]
}
return strings.Join(words, " ")
}impl Solution {
pub fn reverse_words(s: String) -> String {
s.split_whitespace().rev().collect::<Vec<&str>>().join(" ")
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Split and Reverse Approach | Time Complexity: O(N), where N is the number of characters in the string. Space Complexity: O(N), due to storage needed for the split words. |
| In-place Char Array Reversal | Time Complexity: O(N), processing each character multiple times. Space Complexity: O(1), in-place within the character array. |
| Two Pointers | – |
| String Split | – |
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. |
Frequently asked questions
Is Reverse Words in a String easy or hard?
The problem is rated Medium because it requires careful handling of spaces and string boundaries. The basic idea of reversing words is straightforward, but implementing the in-place version with correct pointer movement and space trimming adds moderate complexity.
How to solve Reverse Words in a String in O(n)?
Traverse the string once to extract words or clean spaces, then reverse their order. With the split method, split the string into words, reverse the list, and join with spaces. With the in-place method, reverse the entire string and then reverse each word using two pointers. Both methods ensure every character is visited only a few times, giving O(n) time.
Reverse Words in a String Python or Java solution
In Python, the simplest solution uses `" ".join(reversed(s.split()))`, which splits the string into words and joins them in reverse order. In Java, you can use `String.split()` to create an array of words, reverse the array, and rebuild the string using `StringBuilder`. Both implementations run in O(n) time.
What is the best approach for Reverse Words in a String?
Two common solutions exist. The easiest is the split-and-reverse approach where you split the string into words, reverse the list, and join them back together. This runs in O(n) time and O(n) space. A more optimized method reverses the entire character array and then reverses each word using two pointers, achieving O(n) time and O(1) extra space.
Is Reverse Words in a String asked at Google/Amazon/Meta?
Reverse Words in a String appears frequently in interviews at large tech companies because it tests string manipulation and pointer logic. Variants of the problem have been reported in interviews at Amazon, Google, Meta, and Microsoft. Interviewers often expect candidates to handle edge cases like extra spaces and in-place transformations.
What data structure is used in Reverse Words in a String?
The split-and-reverse approach uses a dynamic array or list to store words temporarily. The optimized approach works directly on a character array and uses two pointers to reverse segments in place. Both solutions rely primarily on string processing and pointer traversal.
What is the time complexity of Reverse Words in a String?
The optimal time complexity is O(n), where n is the length of the string. Each character is processed a constant number of times during splitting, reversing, or pointer traversal. Both the split-and-reverse approach and the in-place reversal method achieve linear time complexity.