Reverse Words in a String

This challenge asks you to reverse the order of words in a given string. This is a common string manipulation problem with applications in text processing, data cleaning, and natural language processing, where the order of words might need to be adjusted for various reasons. Your task is to write an algorithm that efficiently reverses the words while preserving the original characters within each word.

Problem Description

You are given a string s containing multiple words separated by single spaces. The task is to reverse the order of these words in the string. A "word" is defined as a contiguous sequence of non-space characters. Leading or trailing spaces should be removed, and multiple spaces between words should be reduced to a single space.

What needs to be achieved:

• Reverse the order of words in the input string.
• Remove leading and trailing spaces.
• Reduce multiple spaces between words to a single space.

Key Requirements:

• The solution should handle strings with leading/trailing spaces and multiple spaces between words correctly.
• The solution should preserve the original characters within each word.
• The solution should be efficient in terms of time and space complexity.

Expected Behavior:

The function should take a string as input and return a new string with the words reversed and formatted as described above.

Edge Cases to Consider:

• Empty input string.
• String containing only spaces.
• String with leading and trailing spaces.
• String with multiple spaces between words.
• String with a single word.

Examples

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"
Explanation: The words "the", "sky", "is", and "blue" are reversed, and the spaces are adjusted to have only one space between words.

Example 2:

Input: "  hello world  "
Output: "world hello"
Explanation: Leading and trailing spaces are removed, and multiple spaces between "hello" and "world" are reduced to a single space.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: Multiple spaces between "good" and "example" are reduced to a single space.

Example 4:

Input: ""
Output: ""
Explanation: Empty string input results in an empty string output.

Example 5:

Input: "   "
Output: ""
Explanation: String containing only spaces results in an empty string output.

Constraints

• The input string s will contain only characters and spaces.
• The length of the input string s will be between 0 and 50,000 characters, inclusive.
• The time complexity of your solution should be O(n), where n is the length of the input string.
• The space complexity of your solution should be O(n) in the worst case (e.g., when the input string contains only spaces).

Notes

Consider using string splitting and joining techniques to simplify the process. Think about how to efficiently handle the removal of leading/trailing spaces and the reduction of multiple spaces between words. Pseudocode is encouraged to outline your approach before implementing a solution in a specific programming language. A two-pass approach (one to clean the string, one to reverse) is often effective.