151. Reverse Words in a String

Given a string, reverse the order of its words (with each word’s internal characters remaining in their original order). The result must not contain leading/trailing spaces, and consecutive words must be separated by exact one space.

Examples:

• Input: "the sky is blue"
  Output: "blue is sky the"
• Input: " hello world! "
  Output: "world! hello" (extraneous spaces are removed)
• Input: "a good example"
  Output: "example good a" (multiple spaces between words are reduced to one)

Approach

The solution involves three main steps:

1. Remove Extra Spaces: Use a two-pointer (fast and slow) technique to eliminate leading/trailing spaces and reduce consecutive spaces between words to one.
2. Reverse the Entire String: This reverses the order of all characters (temporarily reversing the word order).
3. Reverse Each Word: Reverse each individual word to restore their original character order.

Key Function: removeExtraSpaces

This function trims spaces and ensures a single space between words:

void removeExtraSpaces(string& str) {
    int slow = 0; // Tracks the position for valid characters
    for (int fast = 0; fast < str.size(); ++fast) {
        if (str[fast] != ' ') { // Process non-space characters
            if (slow != 0) { // Add a space before the next word (except first)
                str[slow++] = ' ';
            }
            // Copy the current word (all consecutive non-spaces)
            while (fast < str.size() && str[fast] != ' ') {
                str[slow++] = str[fast++];
            }
        }
    }
    str.resize(slow); // Resize to the length of the processed string
}

Complete Solution Code

class Solution {
public:
    void removeExtraSpaces(string& s) {
        int slow = 0;
        for (int fast = 0; fast < s.size(); ++fast) {
            if (s[fast] != ' ') {
                if (slow != 0) {
                    s[slow++] = ' ';
                }
                while (fast < s.size() && s[fast] != ' ') {
                    s[slow++] = s[fast++];
                }
            }
        }
        s.resize(slow);
    }

    void reverseSegment(string& s, int start, int end) {
        for (int i = start, j = end; i < j; ++i, --j) {
            swap(s[i], s[j]);
        }
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);       // Step 1: Clean up spaces
        reverseSegment(s, 0, s.size() - 1); // Step 2: Reverse entire string

        int wordStart = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { // End of a word
                reverseSegment(s, wordStart, i - 1);
                wordStart = i + 1;
            }
        }
        return s;
    }
};

Right Rotate String

The right rotation of a string moves the last k characters to the front. Given a string s and a positive integer k, move the last k characters to the front.

Example:

Input:

2  
abcdefg  

Output: fgabcde

Approach

To solve this, reverse the entire string, then reverse the first k characters, and finally reverse the remaining characters. This prseerves the order within each segment while rotating the string.

Solution Code

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int rotation;
    string input;
    cin >> rotation >> input;

    reverse(input.begin(), input.end());            // Reverse entire string
    reverse(input.begin(), input.begin() + rotation); // Reverse first k chars
    reverse(input.begin() + rotation, input.end()); // Reverse remaining chars

    cout << input << endl;
    return 0;
}