186. Reverse Words in a String II

Given a character array 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 a single space. Your code must solve the problem in-place, i.e., without allocating extra space.

Example 1:
Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2:
Input: s = ["a"]
Output: ["a"]

Constraints:
1 <= s.length <= 10⁵

s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
There is at least one word in s.
s does not contain leading or trailing spaces.
All the words in s are guaranteed to be separated by a single space.

Approach 1: Reverse the Whole String and Then Reverse Each Word

To have this problem in an Amazon interview is a good situation, since input is a mutable structure and hence one could aim for an O(1) space solution without any technical difficulties. The idea is simple: reverse the whole string and then reverse each word.

Algorithm

Let's first implement two functions:

• reverse(l: list, left: int, right: int): Reverses array characters between left and right pointers. C++ users could directly use built-in std::reverse.
• reverse_each_word(l: list): Uses two pointers to mark the boundaries of each word and the previous function to reverse it.

Now reverseWords(s: List<str>) implementation is straightforward:

• Reverse the whole string: reverse(s, 0, len(s) - 1).
• Reverse each word: reverse_each_word(s).

class Solution {
    public void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

    public void reverseEachWord(char[] s) {
        int n = s.length;
        int start = 0, end = 0;

        while (start < n) {
            // go to the end of the word
            while (end < n && s[end] != ' ') ++end;
            // reverse the word
            reverse(s, start, end - 1);
            // move to the next word
            start = end + 1;
            ++end;
        }
    }

    public void reverseWords(char[] s) {
        // reverse the whole string
        reverse(s, 0, s.length - 1);

        // reverse each word
        reverseEachWord(s);
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the input character array s. The algorithm performs two main operations:

• Reversing the entire string once, which takes O(N) time.
• Reversing each word individually, which also takes O(N) time as each character is reversed exactly once.

Space Complexity: O(1) because the solution modifies the input array in-place. No extra space is allocated other than a few pointers, regardless of the size of the input string.