Задача с собеседования в Яндекс

Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __hello_my___dear_world_ -> __world_dear___my_hello_

Наш чат алгоритмистов

Решение:
Мы сохраняем следующую инфу из строки: слова (подряд идущие непробельные символы) и пробелы (их количество после каждого слова + отдельно ведущие и конечные пробелы).
После этого мы можем взять все слова в обратном порядке, а пробелы вставить ровно так, как они шли в исходной строке.

Код:
string reverseWordsKeepSpaces(const string &s) {
int n = (int)s.size();
int i = 0;

// 1) leading spaces
int leading = 0;
while (i < n && s[i] == ' ') { ++leading; ++i; }

vector<string> words;
vector<int> spacesAfter; // spaces after each word; последний элемент = trailing spaces

// 2) collect words and following spaces counts
while (i < n) {
int j = i;
while (j < n && s[j] != ' ') ++j;
words.emplace_back(s.substr(i, j - i));

int cnt = 0;
int k = j;
while (k < n && s[k] == ' ') { ++cnt; ++k; }
spacesAfter.push_back(cnt);

i = k;
}

// если никаких слов (только пробелы или пустая строка) — вернуть как есть
if (words.empty()) return s;

// trailing spaces — последний элемент spacesAfter
int trailing = spacesAfter.back();
spacesAfter.pop_back(); // теперь spacesAfter.size() == words.size()-1

// 3) формируем результат: leading + reversed words interleaved с spacesAfter (в том же порядке) + trailing
string res;
res.reserve(n);
res.append(leading, ' ');

int m = (int)words.size();
for (int idx = 0; idx < m; ++idx) {
// берем слова с конца: words[m-1], words[m-2], ...
res += words[m - 1 - idx];
if (idx < (int)spacesAfter.size()) {
res.append(spacesAfter[idx], ' ');
}
}
res.append(trailing, ' ');
return res;
}

Асимптотика O(N)

@algoses