Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    MediumTwo PointersStrings

    Reverse Words in a String

    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 <= 10^4
    • s contains 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?
    View original on LeetCode ↗

    The reversal itself is easy — collect the words, flip the list, join. The real problem is whitespace: the input can begin, end, or double up on spaces, but the answer must have exactly one space between words and none at the edges. So the scan has to consume every space without ever emitting one, and re-insert a single separator only at join time. Both solutions below cut the string into whole words, which makes that contract automatic.

    Brute Force: Rebuild by Prepending

    Time O(n²)Space O(n)

    Accumulate characters into the current word. When a space ends the word, glue it onto the front of result instead of the back. Every word therefore lands in front of all the words read before it, and the final string comes out in reverse order. The guard elif word: is the whitespace fix: a space only contributes a word if one is actually pending, so leading, trailing, and repeated spaces produce no empty words and no doubled spaces.

    class Solution:
        def reverseWords(self, s: str) -> str:
            result = ""
            word = ""
            for ch in s:
                if ch != " ":
                    word += ch
                elif word:
                    result = word + (" " + result if result else "")
                    word = ""
            if word:
                result = word + (" " + result if result else "")
            return result

    Why it is quadratic: prepending copies the entire accumulated result every time a word is appended. With roughly n / 2 single-character words the copy costs sum to 1 + 2 + ... + n / 2, which is O(n²). The final output itself needs O(n) space, and word is bounded by the longest run of non-space characters.

    Two-Pointer Scan and Reverse

    OptimalTime O(n)Space O(n)

    Scan with two pointers and cut the string once. i finds the next word start by skipping spaces; j then finds the first space after it. The slice s[i:j] is exactly one word, so it is appended with no trimming and i jumps to j. Because i only ever moves forward and skips every space before a word, empty words can never appear: leading spaces are skipped before the first word, trailing spaces are skipped after the last one, and runs of spaces collapse to a single skip. Reverse the collected list once and join it with single spaces — the join is the only place a space is ever written.

    class Solution:
        def reverseWords(self, s: str) -> str:
            words = []
            i, n = 0, len(s)
            while i < n:
                while i < n and s[i] == " ":
                    i += 1
                if i < n:
                    j = i
                    while j < n and s[j] != " ":
                        j += 1
                    words.append(s[i:j])
                    i = j
            words.reverse()
            return " ".join(words)

    Python’s str.split() with no argument is this same scan with the whitespace handling pushed into the standard library, so " ".join(reversed(s.split())) is a valid one-liner. The follow-up asks for an in-place version: reverse the whole string, reverse each word in its new position, then compact the interior spaces — but that requires a mutable buffer, which a Python str is not.

    Watch the scan cut one word at a time, then the list flip in a single step before the join:

    start

    Input

    the␣sky␣is␣blue

    Words (read order)

    —

    Reversed (output order)

    —

    Output

    —

    words are collected in input order, reversed once, then joined with single spaces

    1 / 10
    currentseenresult

    Two pointers scan left to right: i marks the next word start and j finds its end. Spaces are skipped before every word, so only non-space runs become words.

    Why it is linear: i and j only move forward and together visit each index at most a constant number of times, so the scanning is O(n); the slices and the final join also total O(n). The word list holds O(n) characters in the worst case (every character a one-letter word), and the returned string is O(n), giving O(n) space.

    More Two Pointers practice