Skip to main content
DSA patterns

Reverse Words in a String

mediumStringsAmazonAccentureInfosys

Problem statement

You're given a string of words separated by spaces. Return a new string with the words in reverse order, so the last word comes first and the first word comes last. The words themselves are never rearranged internally — only their order in the sentence changes.

The input can have extra spaces: more than one space between words, or spaces at the very start or end. The output must have exactly one space between words and no spaces at the start or end.

This shows up whenever a tool hands you tokens in one order and you need them in the other — for example a breadcrumb path (prod > api > payments) that a UI wants shown newest-first, or a log line where fields were appended in the wrong order by an upstream service.

Examples

Example 1

Input: s = "the sky is blue"

Output: blue is sky the

Explanation: Each word keeps its own letters; only the order the four words appear in changes.

Example 2

Input: s = " hello world "

Output: world hello

Explanation: The leading and trailing spaces around hello world are dropped entirely — the output never starts or ends with a space.

Hints

Hint 1: Whatever technique you use, the words themselves never change — only the order they come out in. Think about processing the string from the end so words naturally come out in reverse order.

Approach

Optimal: In-place double reversal

Intuition

This is the classic trick for solving this problem with a mutable string type (a char[] in Java or C++) and no extra list of words at all. The insight: reversing the whole string flips the order of the words for free, but it also reverses the letters inside each word. So you undo that second effect by reversing each word back into shape, one word at a time, after the big reversal.

Before any of that, you still need to deal with spacing: multiple spaces between words, and leading/trailing spaces, would otherwise become garbled after two reversals. So the first step compacts the string down to single spaces between words with nothing at either end — the same shape the output needs to have — and only then do the two reversals run on that cleaned-up string.

Steps

  1. Compact spaces in place using a fast/slow pointer: copy each word forward, and insert exactly one space before each word after the first one; skip every space you encounter along the way. This shrinks the usable length of the array down to write, the new length with clean single spacing.
  2. Reverse the entire compacted range, from index 0 to write - 1.
  3. Walk through that reversed range and reverse each individual word back to its normal letter order — the word boundaries are now marked by the single spaces from step 1.
  4. Return the string built from the first write characters.

Dry run

s = " the sky "

step array contents (after)
after compacting spaces "the sky" (length 7)
after reversing everything "yks eht"
after reversing each word "sky the"

Edge cases: a string of only spaces compacts down to length 0, so both reversal steps run on an empty range and the result is an empty string. A single word with no internal spaces reverses twice and ends up unchanged.

Complexity

Time O(n) - Compacting the spaces is one pass over the string. Reversing the whole compacted string is another pass. Reversing each word back is a third pass that, across all words together, also touches each character exactly once. Three linear passes still add up to O(n).

Space O(1) - extra — Beyond the string itself (which in Java and C++ we edit in place as a mutable character array), we only use a handful of index variables. Python's strings are immutable, so there we convert to a list of characters first, which costs O(n) — but the algorithm itself needs no extra space proportional to the input, which is the point the follow-up below is asking about.

class Solution:
    def reverseWords(self, s: str) -> str:
        chars = list(s)
        n = len(chars)

        write = 0
        read = 0
        while read < n:
            if chars[read] != ' ':
                if write != 0:
                    chars[write] = ' '
                    write += 1
                while read < n and chars[read] != ' ':
                    chars[write] = chars[read]
                    write += 1
                    read += 1
            else:
                read += 1
        chars = chars[:write]
        n = write

        def reverse_range(lo, hi):
            while lo < hi:
                chars[lo], chars[hi] = chars[hi], chars[lo]
                lo += 1
                hi -= 1

        reverse_range(0, n - 1)

        start = 0
        for i in range(n + 1):
            if i == n or chars[i] == ' ':
                reverse_range(start, i - 1)
                start = i + 1

        return ''.join(chars)


if __name__ == "__main__":
    print(Solution().reverseWords("the sky is blue"))  # blue is sky the
    print(Solution().reverseWords("  hello world  "))  # world hello
RecapThe whole problem in a few lines, for the night before
  • Spot it: reverse the order of words, with messy spaces in the input
  • Idea: split on whitespace (which drops extra spaces), reverse the list of words, join with a single space
  • Cost: O(n) time, O(n) space
  • Trap: leading, trailing and repeated spaces must not show up in the output

Interview follow-ups

  • The words are separated by commas instead of spaces, and commas should stay commas in the output.

    Change the word-boundary check from == ' ' to == ',' everywhere it appears, and join with "," instead of ' ' at the end. The compacting and reversal logic doesn't change at all — it only cares that there's some single delimiter character marking where one word ends and the next begins. Time and space stay the same.

  • The input is a huge string that doesn't fit in memory, streamed in chunks.

    You can't reverse a stream in a single forward pass, because the last word you'll ever see needs to come out first. A practical approach is to make one pass that records the byte offset of each word (not the word itself), then a second pass, reading backward from the end of the file, that seeks to each recorded offset and streams that word out. This trades one extra pass and some seeking for keeping memory at O(1) per word instead of O(n) for the whole string.

Frequently asked questions

Splitting on a single literal space character keeps empty strings for every extra space — "a b".split(" ") gives ["a", "", "b"] in many languages. The whitespace-collapsing form of split (no argument in Python, or a \s+ regex in Java) is what discards those empty entries automatically, which is exactly the cleanup this problem needs.

Only where strings are mutable. In Java and C++ you can edit the char[] or std::string directly, so the only extra memory is a few index variables — true O(1) extra space. In Python, strings can't be modified in place, so you first copy the string into a list of characters, which costs O(n). The algorithm's logic is still the O(1)-extra-space one; Python just needs a mutable copy to run it on.

Reordering space- or delimiter-separated tokens comes up whenever a UI or downstream system wants fields in the opposite order from how an upstream system emitted them — breadcrumb paths, reversed timestamps in a filename, or normalizing arguments passed in the wrong order between two tools in a pipeline.