Reverse Words in a String

Q: What is the time complexity of Reverse Words in a String?

Both approaches run in O(n) time for a string of length n , because each character is read and written a constant number of times. Splitting uses O(n) extra space for the list of words. Reversing the whole string and then each word needs O(1) extra space on a character array you may edit.

MediumArrays and strings Two pointers

+10

You get a string s made of words and spaces. A word is a run of letters and digits with no space inside it. Words can be separated by more than one space, and s can start or end with spaces.

Return the words in reverse order, joined by exactly one space, with no space at the start or the end. Each word keeps its spelling; only the order of the words changes.

Function

reverseWords(s: string) → string

sstring: letters, digits and spaces holding at least one word
Returnsstring: the words of s in reverse order, separated by single spaces

Constraints

1 ≤ s.length ≤ 10⁴
s contains only English letters, digits and spaces.
s holds at least one word.

Examples

Input: s = "Coddy runs in 15 languages"
Output: "languages 15 in runs Coddy"
Explanation: The words are Coddy, runs, in, 15 and languages. Read from last to first they give languages 15 in runs Coddy; 15 counts as a word because words may hold digits.

Input: s = " practice makes progress "
Output: "progress makes practice"
Explanation: The spaces at both ends are dropped, and the runs of two and three spaces between the words shrink to one. The three words come out last to first: progress makes practice.

Input: s = " single "
Output: "single"
Explanation: A list of one word reads the same in reverse. Only the spaces around it go, so the answer is single.

Follow-up

Can you reverse the words but keep the spacing of s: the same runs of spaces, with the same lengths, in the same order?

Solution

The word order is one reversal; the spaces are where solutions break. Spaces at either end and repeated spaces between words must disappear, with exactly one space between words in the answer. You can split into a list of words, or reverse the whole string and then each word inside one array.

Split into words and join them in reverse

Intuition

Cut s into its words, reverse the list and join it with single spaces. The cutting needs care: splitting " practice makes progress " at every single space gives six empty pieces around the three words. Drop the empty pieces and the list is practice, makes, progress.

The split reads each character once and the join writes each kept character once, so the time is O(n) for a string of length n. The list of words and the answer take O(n) extra space.

Algorithm

Split s on spaces.
Drop the empty pieces.
Reverse the list of words.
Join the words with one space between each and return the result.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Reverse the whole string, then each word

Intuition

Reversing the whole string puts the words in the right order but spells each one backwards: Coddy runs in 15 languages becomes segaugnal 51 ni snur yddoC. Reversing each word on its own then gives languages 15 in runs Coddy.

The spaces go in the same pass. A read index walks the reversed array and skips spaces; a write index marks where the next kept character goes. Copying never overwrites a character you still need, because write never passes read: the one space written before a word stands in for at least one space that read skipped.

Each character is copied at most once and swapped at most twice, so the time is O(n), with O(1) extra space on a character buffer you may edit. Strings here arrive as values, so each solution makes one working copy of s: O(n) memory in total.

Algorithm

Copy s into a character array and reverse the whole array.
Walk the array with a read index and skip spaces.
At each word, write one space first unless it is the first word, then copy the word's characters to the write index.
Reverse the stretch you copied so the word reads forwards.
Return the first write characters.

def reverseWords(s):
    chars = list(s)

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

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Pitfalls and edge cases

Splitting on a single space and keeping every piece. "a b" splits into a, an empty piece and b, and the join puts two spaces back: "b a".
Trusting a split to drop the ends. Java's split(" ") drops empty pieces at the end but keeps them at the start, so " a b" still leaves one.
Adding a space after every word, the last one included, so the answer ends with a space. Put the space before every word except the first.
Doing only one reversal in the in-place version. Reversing only the words gives yddoC snur ni 51 segaugnal.
In PHP and R, an all-digit input such as 2026 may arrive as a number. Turn it into a string before splitting.

Frequently asked questions3

What is the time complexity of Reverse Words in a String?

Both approaches run in O(n) time for a string of length n, because each character is read and written a constant number of times. Splitting uses O(n) extra space for the list of words. Reversing the whole string and then each word needs O(1) extra space on a character array you may edit.

How do you handle multiple spaces between words?

Treat a word as a run of non-space characters and never copy spaces from the input. A split with no separator in Python and Ruby, strings.Fields in Go and split_whitespace in Rust already skip every run of spaces and both ends; elsewhere, drop the empty pieces. Then write one space between words.

Can you reverse the words without a split function?

Yes. Scan from the right end: skip spaces, mark where a word ends, move left to its start, and append the word with a space before it unless it is the first. Each character is visited once, so the time stays O(n), and the words come out in reverse order with no list to reverse.

def reverseWords(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "Coddy runs in 15 languages"

Expected Output

"languages 15 in runs Coddy"