Reverse Words in a String

Description

151. 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\le \text{s.length}\le 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?

---

Approach 1: Built-in Regex & Reverse ($O(N)$ Time, $O(N)$ Space)

Intuition

Trim leading and trailing spaces from s, split the string by one or more spaces (\s+), and traverse the resulting array in reverse order to build the new string.

class Solution {
    public String reverseWords(String s) {
        // Trim leading and trailing spaces
        s = s.trim();
        
        // Split by one or more spaces
        String[] words = s.split("\\s+");
        
        StringBuilder result = new StringBuilder();
        // Traverse words in reverse order
        for (int i = words.length - 1; i >= 0; i--) {
            result.append(words[i]);
            if (i > 0) {
                result.append(" ");
            }
        }
        
        return result.toString();
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Trimming, regex splitting, and iterating through the words array all scale linearly with input string length $N$.
• Space Complexity: $O(N)$ — Required to store the split array of strings and output StringBuilder.

---

Approach 2: Two-Pointer Backward Scan ($O(N)$ Time, $O(N)$ Space) - Use this

Intuition

Scan the string backwards from end to start using two pointers to locate each word without relying on heavy regular expressions:

1. Skip trailing spaces.
2. Place pointer j at the end of a word and decrement i until reaching a space to find the start of the word (i + 1).
3. Extract s.substring(i + 1, j + 1) and append it to StringBuilder.

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int i = s.length() - 1;
 
        while (i >= 0) {
            // Skip spaces to reach end of current word
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            if (i < 0) break;
 
            int j = i; // End of current word
 
            // Move i to find start of current word
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
 
            // Append space separator between words
            if (sb.length() > 0) {
                sb.append(" ");
            }
 
            // Extract word from substring
            sb.append(s.substring(i + 1, j + 1));
        }
 
        return sb.toString();
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single pass scan over string s of length $N$.
• Space Complexity: $O(N)$ — Space allocated for the output string.

1. Single (' ') vs. Double (" ") Quotes

• ' ' (Single Quotes): Represents a **primitive char**. Required when comparing values with s.charAt(i) because charAt() returns a char.
• " " (Double Quotes): Represents a String object. Used for text sequences (e.g., sb.append(" ")).

2. substring(beginIndex, endIndex) Rules

• Rule: [Inclusive, Exclusive)

• beginIndex: Included

• endIndex: Excluded

• Why j + 1 in code: s.substring(i + 1, j + 1) starts at index i + 1 and stops right before j + 1, successfully including the character at index j.

---

Approach 3: In-Place Reverse Simulation (Follow-Up Answer)

Intuition

If strings are treated as mutable arrays (e.g., char[] in Java or std::string in C++):

1. Reverse the entire string.
2. Reverse each word in place back to its original spelling.
3. Clean up extra spaces by shifting characters left.

class Solution {
    public String reverseWords(String s) {
        char[] a = s.toCharArray();
        int n = a.length;
 
        // Step 1: Reverse the entire character array
        reverse(a, 0, n - 1);
 
        // Step 2 & 3: Reverse each word back and compress extra spaces
        return cleanSpacesAndReverseWords(a, n);
    }
 
    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    }
 
    private String cleanSpacesAndReverseWords(char[] a, int n) {
        int i = 0, j = 0;
 
        while (j < n) {
            while (j < n && a[j] == ' ') j++;             // Skip spaces
            int start = i;
            while (j < n && a[j] != ' ') a[i++] = a[j++]; // Copy word
            if (start < i) {
                reverse(a, start, i - 1);                 // Reverse word back
                if (i < n) a[i++] = ' ';                   // Add single space separator
            }
        }
 
        // Remove trailing space if exists
        if (i > 0 && a[i - 1] == ' ') i--;
 
        return new String(a, 0, i);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Linear operations for reversing and shifting characters.
• Space Complexity: $O(N)$ in Java (due to char[] conversion because Java strings are immutable), but $O(1)$ auxiliary space in languages with mutable native strings (like C++).

---

Easy Memory Rule

“To reverse words in a string, either scan backward with Two Pointers to pick words directly, or reverse the WHOLE string first and then reverse each individual word back!”