#151

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse Words in a String

Reverse Words in a String requires reordering words using precise two-pointer scanning with careful space handling for efficiency.

two pointers string

Problem Statement

Given a string s, reverse the order of words. Words are sequences of non-space characters separated by one or more spaces. You must return a single string with words in reverse order separated by a single space, removing any leading or trailing spaces.

Implement this in-place or using minimal extra space if possible. Extra spaces between words in the original string should be reduced to a single space in the output, preserving only the word order reversal.

Examples

Example 1

Input: s = "the sky is blue"

Output: "blue is sky the"

Example details omitted.

Example 2

Input: s = " hello world "

Output: "world hello"

Your reversed string should not contain leading or trailing spaces.

Example 3

Input: s = "a good example"

Output: "example good a"

You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Solution Approach

Trim and Normalize Spaces

First, remove leading and trailing spaces and reduce multiple spaces between words to a single space. This normalization ensures two-pointer scanning can reliably detect word boundaries without extra checks.

Two-Pointer Word Extraction

Use two pointers to scan from the end of the string to the beginning. Identify word boundaries by detecting transitions from spaces to non-space characters. Collect words in reverse order as you scan to construct the final output efficiently.

Build Result String

After collecting words in reverse order, join them with a single space. Ensure no extra spaces are added, and verify that edge cases like single-word strings or multiple consecutive spaces are correctly handled.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is scanned at most twice during trimming and reversal. Space complexity is O(n) if a new string is constructed, or O(1) extra if in-place operations are performed with careful pointer management.

What Interviewers Usually Probe

Watch for hidden leading and trailing spaces in the input string.
Check if candidates correctly reduce multiple spaces between words to a single space.
Ensure candidates use a two-pointer approach rather than naive split and reverse methods.

Common Pitfalls or Variants

Common pitfalls

Failing to trim leading or trailing spaces before scanning.
Incorrectly handling multiple consecutive spaces between words.
Building the output string with extra spaces at the start or end.

Follow-up variants

Reverse words in a string in-place without allocating extra arrays.
Handle Unicode or non-ASCII whitespace characters during reversal.
Reverse words while preserving the original capitalization or punctuation.

FAQ

What is the best approach to reverse words in a string efficiently?

Using a two-pointer scanning method to locate word boundaries and collect words in reverse order minimizes both time and space complexity.

How do I handle multiple spaces between words in the input?

Normalize spaces by trimming leading/trailing spaces and reducing multiple consecutive spaces to a single space before scanning.

Can this be done in-place without extra memory?

Yes, with careful two-pointer swapping and tracking word boundaries, in-place reversal is possible while maintaining correct spacing.

Why is trimming spaces important for this problem?

Trimming ensures accurate detection of word boundaries and prevents extra spaces in the final reversed string.

Does GhostInterview suggest patterns specific to Reverse Words in a String?

Yes, it focuses on two-pointer scanning and invariant tracking, highlighting common errors unique to this word reversal pattern.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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
        return " ".join(words[::-1])

Solution 2: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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
        return " ".join(words[::-1])

Continue Practicing

#165 compare version numbers #125 valid palindrome #28 find the index of the first occurrence in a string