What it teaches: Reversing at two levels (the whole string, then each word), plus cleaning up extra spaces.
Practise it on judges as “Reverse Words in a String”.
The problem
Given a string s, reverse the order of its words. A word is a sequence of non-space characters. Return a string with the words in reverse order, separated by single spaces, with no leading or trailing spaces.
Example 1
Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2
Input: s = " hello world "
Output: "world hello"
Example 3
Input: s = "a good example"
Output: "example good a"
Constraints
1 ≤ s.length ≤ 10⁴
s contains letters, digits and spaces
There is at least one word
Pattern clues in the wording
→ Reverse order of blocks while keeping each block's own order
→ Extra spaces to clean up
These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
return sb.toString();
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Trim, split on runs of whitespace, then join the words from last to first with single spaces.
Approach 1
class Solution {
public 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();
}
}
Verdict: Short and fine in most interviews; mention that split takes a regular expression.
2
Optimal: scan from the end with two pointers
Time O(n) Space O(n) for the output
Walk i from the last character backwards. Skip spaces. When you hit a word's last character, set end = i, then move i left to the word's start. Append s.substring(i + 1, end + 1) to the result, with a space before every word except the first.
▶ Dry run: Finding words from the rights = "hi you"
h
0
i
1
2
3
y
4
o
5
u
6
↑i
result(list)
empty
Step 1/4i is on 'u', a word character: mark end = 6.
Approach 2
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
int i = s.length() - 1;
while (i >= 0) {
while (i >= 0 && s.charAt(i) == ' ') i--; // skip spaces
if (i < 0) break;
int end = i;
while (i >= 0 && s.charAt(i) != ' ') i--; // find the word's start
if (sb.length() > 0) sb.append(' ');
sb.append(s, i + 1, end + 1);
}
return sb.toString();
}
}
Verdict: One pass with no regex or intermediate array of words.
Before you submit
Edge cases and common mistakes
Test these inputs
Leading and trailing spaces
Multiple spaces between words
A single word
Single-character words
Mistakes people make
Splitting on " ", which leaves empty strings between consecutive spaces.
Adding a trailing space after the last word.
Interview
Follow-up questions
How would you do it in place on a char[] with O(1) extra space?
What if words are separated by other whitespace, like tabs?