Course4all
Join us on telegram
Home/dsa/Two Pointers/Reverse Words in a String

Reverse Words in a String

Master this topic with zero to advance depth.

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.

Input: " the sky is blue " Step 1: Trim & Reverse the entire string. "eulb si yks eht" Step 2: Reverse each word in place. "blue is sky the"
Medium

Examples

Input: s = "the sky is blue"
Output: "blue is sky the"

The words are reversed. Extra spaces are removed.

Approach 1

Level I: Built-in Split & Reverse

Intuition

Most languages provide utility functions to split a string by spaces and join them back. This is the most readable way to solve it.

⏱ O(N)💾 O(N)

Detailed Dry Run

" hello world " -> Split -> ["hello", "world"] -> Reverse -> ["world", "hello"] -> Join -> "world hello"

java
public String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    Collections.reverse(Arrays.asList(words));
    return String.join(" ", words);
}

⚠️ Common Pitfalls & Tips

The input may have leading, trailing, or multiple spaces between words.

Approach 2

Level II: Better (In-place Array Modification)

Intuition

To optimize for space (if the string was mutable like an array), we can: 1. Remove extra spaces. 2. Reverse the entire array. 3. Reverse each word individualy.

⏱ O(N)💾 O(N) (In languages where strings are immutable, we still need O(N) space)

Detailed Dry Run

"the sky" → "yks eht" → "sky the"

java
public String reverseWords(String s) {
    char[] a = s.toCharArray();
    int n = a.length;
    reverse(a, 0, n - 1);
    reverseWords(a, n);
    return cleanSpaces(a, n);
}
private void reverse(char[] a, int i, int j) {
    while (i < j) { char t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

⚠️ Common Pitfalls & Tips

Managing multiple spaces and in-place reversal can be tricky index-wise.

Approach 3

Level III: Optimal (Two Pointers - Backwards Traversal)

Intuition

Traverse the string from right to left, identifying words and adding them to a result. This avoids using heavy split/join functions.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: "sky blue"

  1. i=7 ('e'): word end.
  2. Move i to 4 (' '): word start. Word: "blue".
  3. Skip spaces. i=2 ('y'): word end.
  4. Move i to start: Word: "sky". Result: "blue sky"
java
public String reverseWords(String s) {
    StringBuilder res = new StringBuilder();
    int i = s.length() - 1;
    while (i >= 0) {
        if (s.charAt(i) == ' ') { i--; continue; }
        int j = i;
        while (i >= 0 && s.charAt(i) != ' ') i--;
        if (res.length() > 0) res.append(" ");
        res.append(s.substring(i + 1, j + 1));
    }
    return res.toString();
}

⚠️ Common Pitfalls & Tips

Be careful with leading and trailing spaces. The i+1 and j+1 indices are crucial.

← Previous QuestionMinimum Size Subarray Sum
Next Question →Find the Duplicate Number