# Reverse Words in a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reverse-words-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/reverse-words-in-a-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Paytm](https://scaleengineer.com/companies/paytm), [TikTok](https://scaleengineer.com/companies/tiktok), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yelp](https://scaleengineer.com/companies/yelp), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [HPE](https://scaleengineer.com/companies/hpe), [Snap](https://scaleengineer.com/companies/snap), [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## Problem
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 <= 104`
* `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?

# Approaches
## Using Language Built-in Functions
This approach leverages the built-in functions provided by the programming language, such as `trim`, `split`, and `join`, along with collection reversal utilities. It's often the most concise and readable solution for this problem.
**Time:** O(N) · **Space:** O(N)
**Pros:** Very simple and concise, leading to highly readable code.; Leverages optimized and well-tested library functions, reducing the chance of bugs.
**Cons:** Creates intermediate data structures (an array of strings and a list), which can consume significant memory, making it O(N) in space complexity.; May not be allowed in interviews that restrict the use of certain built-in functions to test fundamental algorithm knowledge.
### Explanation
The simplest way to solve this problem is by using high-level, built-in string and collection manipulation functions. The process is straightforward:

1.  **Trim**: The input string `s` can have leading or trailing spaces. `s.trim()` removes these.
2.  **Split**: The trimmed string is then split into words. The key is to use a regular expression like `"\\s+"` as the delimiter, which handles cases with multiple spaces between words, treating them as a single separator.
3.  **Reverse**: The resulting array of words is converted to a list, which is then reversed using `Collections.reverse()`.
4.  **Join**: Finally, `String.join(" ", words)` concatenates the elements of the reversed list into a single string, with each word separated by a single space.

```java
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String reverseWords(String s) {
        // 1. Trim leading and trailing spaces
        String trimmedStr = s.trim();

        // 2. Split by one or more spaces
        String[] words = trimmedStr.split("\\s+");

        // 3. Reverse the array of words
        Collections.reverse(Arrays.asList(words));

        // 4. Join the words with a single space
        return String.join(" ", words);
    }
}
```
### Algorithm
1. Remove leading and trailing whitespace from the input string `s` using `trim()`.
2. Split the trimmed string by one or more spaces (`"\\s+"`) to get an array of words.
3. Create a `List` from the array of words to use the `Collections.reverse()` utility.
4. Reverse the order of elements in the list.
5. Join the words in the reversed list with a single space separator using `String.join()` to form the final string.

## Iterating from Right to Left
This approach avoids using the `split` function by manually iterating through the string from end to beginning. It identifies words one by one and appends them to a `StringBuilder` to construct the reversed string.
**Time:** O(N) · **Space:** O(N)
**Pros:** More memory-efficient than the split-based approach as it avoids creating an intermediate array of strings.; Demonstrates a good understanding of string manipulation and pointer-based logic.
**Cons:** The logic is more complex and requires careful pointer management compared to using built-in functions.; Still requires O(N) extra space for the `StringBuilder`, so it's not the most memory-efficient solution.
### Explanation
Instead of splitting the string into an array, we can build the reversed string directly. By scanning the string from right to left, we encounter the words in the order we need them for the final result (last word first, etc.).

We use a pointer `i` to scan the string from the end. We first skip any spaces to find the end of a word. Then, we find the beginning of that same word. Once we have the word's boundaries, we extract it using `substring` and append it to a `StringBuilder`. We then append a space and continue scanning leftwards for the next word. This method avoids creating an intermediate array of all words at once.

```java
class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int i = s.length() - 1;

        while (i >= 0) {
            // Skip trailing spaces of a word
            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            if (i < 0) break;

            // Find the start of the word
            int j = i;
            while (j >= 0 && s.charAt(j) != ' ') {
                j--;
            }

            // Append the word. If sb is not empty, add a space first.
            if (sb.length() > 0) {
                sb.append(' ');
            }
            // The word is from j+1 to i+1
            sb.append(s.substring(j + 1, i + 1));
            
            // Move i to the position before the current word
            i = j;
        }

        return sb.toString();
    }
}
```
### Algorithm
1. Initialize an empty `StringBuilder` to store the result.
2. Iterate through the input string `s` from right to left using an index `i`.
3. Skip any trailing spaces by decrementing `i`.
4. When a non-space character is found, it marks the end of a word. Use another pointer `j` to find the start of this word by moving leftwards from `i`.
5. Once the word is identified (from `j+1` to `i+1`), append it to the `StringBuilder`.
6. After appending a word, append a single space to the `StringBuilder` before searching for the next word.
7. Continue this process until the beginning of the string is reached.
8. Finally, remove the last appended space from the `StringBuilder` and return the result.

## In-place Reversal with O(1) Space
This is the most optimal approach in terms of space complexity, addressing the follow-up question. It modifies the string (or a character array representation) in-place. The core idea is a three-pass algorithm: first, clean up all extra spaces; second, reverse the entire string; and third, reverse each word individually.
**Time:** O(N) · **Space:** O(1) (for the algorithm itself)
**Pros:** Extremely space-efficient, using O(1) extra space (not counting the initial character array).; An excellent solution for environments with strict memory constraints.; Demonstrates a deep understanding of array manipulation and in-place algorithms, which is highly valued in technical interviews.
**Cons:** The algorithm is significantly more complex to understand and implement correctly.; In languages with immutable strings like Java or Python, an initial O(N) space cost is unavoidable to create a mutable character array. The O(1) space complexity refers to the *extra* space used by the algorithm itself.; The process modifies the character array, which might not be desirable in all situations.
### Explanation
To achieve O(1) extra space, we must perform the reversal in-place on a mutable data structure, like a character array in Java. The algorithm consists of three main steps:

1.  **Clean Spaces**: This pass normalizes the string. We use a write pointer `i` and a read pointer `j`. We iterate through the array, copying words to the front and ensuring only a single space is placed between them. This effectively removes all unwanted spaces and gives us a new, shorter effective length for the string.
2.  **Reverse the Entire Array**: We reverse all characters in the cleaned-up portion of the array. For example, `"the sky is blue"` becomes `"eulb si yks eht"`.
3.  **Reverse Each Word**: We iterate through the array one last time. We find the start and end of each word (now separated by single spaces) and reverse them. `"eulb"` becomes `"blue"`, `"si"` becomes `"is"`, and so on. This restores the words to their correct spelling while keeping their reversed order.

```java
class Solution {
    public String reverseWords(String s) {
        if (s == null) return null;

        char[] a = s.toCharArray();
        int n = a.length;

        // Step 1: Reverse the entire string
        reverse(a, 0, n - 1);

        // Step 2: Reverse each word
        reverseWords(a, n);

        // Step 3: Clean up spaces
        return cleanSpaces(a, n);
    }

    // Helper to reverse a sub-array
    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    }

    // Helper to reverse words in the array
    private void reverseWords(char[] a, int n) {
        int i = 0, j = 0;
        while (i < n) {
            // Skip spaces to find the start of a word
            while (i < n && a[i] == ' ') i++;
            j = i;
            // Find the end of the word
            while (j < n && a[j] != ' ') j++;
            // Reverse the word
            reverse(a, i, j - 1);
            i = j;
        }
    }

    // Helper to clean up spaces
    private String cleanSpaces(char[] a, int n) {
        int i = 0, j = 0;
        while (j < n) {
            // Skip spaces
            while (j < n && a[j] == ' ') j++;
            // Copy word
            while (j < n && a[j] != ' ') a[i++] = a[j++];
            // Skip spaces
            while (j < n && a[j] == ' ') j++;
            // Add one space after a word if it's not the end
            if (j < n) a[i++] = ' ';
        }
        return new String(a).substring(0, i);
    }
}
```
*Note: The provided code implements a slightly different but equally valid 3-step in-place logic (Reverse All -> Reverse Words -> Clean Spaces) which is also a common way to solve it.*
### Algorithm
1. **(Clean Spaces)**: Convert the string to a `char[]`. Use a two-pointer approach (read and write pointers) to create a compact sequence of words at the beginning of the array, separated by single spaces. This removes all leading, trailing, and extra intermediate spaces. Keep track of the new, shorter length.
2. **(Reverse All)**: Reverse the entire cleaned-up portion of the character array. After this step, the words are in the correct order, but each word itself is spelled backward.
3. **(Reverse Words)**: Iterate through the array again. Identify the boundaries of each word (sequences of non-space characters) and reverse each word in-place.
4. **(Final String)**: Create a new string from the modified character array, using the new length calculated in the first step.

# Solutions
### CSharp

```csharp
public class Solution {
    public string ReverseWords(string s) {
        return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse());
    }
}
```

### Java

```java
class Solution {
public
  String reverseWords(String s) {
    List<String> words = Arrays.asList(s.trim().split("\\s+"));
    Collections.reverse(words);
    return String.join(" ", words);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reverseWords(string s) {
    int i = 0;
    int j = 0;
    int n = s.size();
    while (i < n) {
      while (i < n && s[i] == ' ') {
        ++i;
      }
      if (i < n) {
        if (j != 0) {
          s[j++] = ' ';
        }
        int k = i;
        while (k < n && s[k] != ' ') {
          s[j++] = s[k++];
        }
        reverse(s.begin() + j - (k - i), s.begin() + j);
        i = k;
      }
    }
    s.erase(s.begin() + j, s.end());
    reverse(s.begin(), s.end());
    return s;
  }
};

```

### Python

```python
class Solution:
    def reverseWords(self, s: str) -> str: words = s . strip(). split() return ' ' . join(words[:: - 1])  # class Solution : # O(1) space complexity def reverseWords ( self , s : str ) -> str : # Remove leading and trailing spaces s = s . strip () # Reverse the entire string s = self . reverseString ( s , 0 , len ( s ) - 1 ) # Reverse each word in the string start = 0 end = 0 while end < len ( s ): if s [ end ] == ' ' : s = self . reverseString ( s , start , end - 1 ) start = end + 1 end += 1 # Reverse the last word s = self . reverseString ( s , start , end - 1 ) return s def reverseString ( self , s : str , start : int , end : int ) -> str : # Convert the string to a list of characters chars = list ( s ) # Reverse the substring while start < end : chars [ start ], chars [ end ] = chars [ end ], chars [ start ] start += 1 end -= 1 # Convert the list of characters back to a string return '' . join ( chars ) ############ class Solution ( object ): def reverseWords ( self , s ): """ :type s: str :rtype: str """ return " " . join ( s . split ()[:: - 1 ])

```