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

Дана строка, состоящая из букв 'X', 'Y' и 'O'.
Нужно найти кратчайшее расстояние между буквами 'X' и 'Y'.
Если хотя бы одна из букв отсутствует — вывести 0. Кстати задачу обсуждали ранее в нашем чате крутых алгоритмистов😎😎

Решение:
Решение за один проход по строке: запоминаем последние позиции X и Y, на каждой итерации обновляем ответ

def shortest_distance(s):
last_x = last_y = -1
min_dist = float('inf')

for i, ch in enumerate(s):
if ch == 'X':
last_x = i
if last_y != -1:
min_dist = min(min_dist, abs(last_x - last_y))
elif ch == 'Y':
last_y = i
if last_x != -1:
min_dist = min(min_dist, abs(last_x - last_y))

return min_dist if min_dist != float('inf') else 0

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

@algoses

Задача с собеседования в лабу СБЕРа

Даны два мультимножества, c одним из них вы можете проводить следующие операции:
1. Выбрать элемент и заменить его на  x * 2.
2. Выбрать элемент и заменить его на  x // 2  (округление вниз).
У вас есть неограниченное количество операций, ваша задача определить возможно ли приравнять второе мультимножество к первому.

Решение:

Обозначим мультимножества как A и B.
1. Для начала заметим выгодное разбиение A на классы эквивалентности x ~ y <=> \exist k >= 0: min(x, y) * 2^k = max(x, y) (иначе говоря если больший элемент может быть получен путём умножения меньшего на степень двойку (т е проводения некоторого количества операций первого типа), то мы будем эти два элемента считать за эквивалентные). То есть нам достаточно проверить множества на равенства меньших элементов из каждого класса (просто каждый элемент множества A будем делить до того момента, пока он делится). Таким образом мы свели задачу к использованию лишь второй операции.

2. Заметим что каждый элемент из множества b порождает с помощью операции 2 ряд различных классов эквивалентности (можно кстати оценить количество этих классов как O(log(x))), тогда нам остаётся лишь распределить выгодно эти классы по элементам из A. Воспользуемся жадным подходом отсортируем множество B, и будем идти от меньшего к большему по элементам и последовательно для каждого элемента перебирать эти классы (то есть просто делить на 2 с округлением и проверять наличие текущего элемента класса в множестве А), в случае если мы нашли элемент совпадающий с элементом из A просто удалим его и закончим перебор классов.

Пример кода (здесь даны множества уже в отсортированном порядке) уже в нашем чате.

Эту задачу нам скинул подписчик в нашем чатике и мы там же оперативно обсудили, присоединяйся в наше комьюнити алгоритмистов!

@algoses

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

Написать метод, который заменит все пробелы в строке на '%20'
На вход подается строка с зарезервированными под расширение символами (гарантируется, что resize() до разумных размеров не будет выделять память)

Ограничения: O(1) по памяти, O(N) по времени, менять исходную строку можно

Решение:
Два прохода по строке: на первом считаем количество пробелов, и таким образом итоговую длину, на втором идем с конца и копируем символы, кодируя в процессе пробелы

def url_encode(char_list, true_length):
space_count = 0
for i in range(true_length):
if char_list[i] == ' ':
space_count += 1

index = true_length + space_count * 2

i = true_length - 1
j = index - 1

if len(char_list) < index:
char_list.extend([''] * (index - len(char_list)))

while i >= 0:
if char_list[i] == ' ':
char_list[j] = '0'
char_list[j - 1] = '2'
char_list[j - 2] = '%'
j -= 3
else:
char_list[j] = char_list[i]
j -= 1
i -= 1

return ''.join(char_list[:index])

@algoses

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

Дан список неотрицательных целых чисел, повторяющихся элементов в списке нет. Нужно преобразовать его в строку, сворачивая соседние по числовому ряду числа в диапазоны
Пример:
[1,4,5,2,3,9,8,11,0] => "0-5,8-9,11"

НАШ ЧАТ

Решение:
Сортировка плюс один проход. По времени за O(nlogn)

def compress_ranges(nums):
if not nums:
return ""

nums.sort()
result = []
start = end = nums[0]

for num in nums[1:]:
if num == end + 1:
end = num
else:
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
start = end = num

if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")

return ",".join(result)

@algoses

Вот и разбор ААА алгосов! Для подготовки к собесам советую присмотреться к нашему курсу по алгоритмам.

@algoses

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

Реализовать функцию fuzzy pussy search как в редакторе sublime text 3.

Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй

fuzzysearch('car', 'cartwheel') -> true

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

Решение:
Один проход по символам строки

def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False

i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False

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

@algoses

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

Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.

Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)

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

Решение:
Пройдемся по строке с разрядами и столбиком умножим число на n. Поддерживаем остаток и считаем так до конца

def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")

num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0

for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10

if carry:
num.append(str(carry))

return ''.join(num)

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

@algoses

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

На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.

Требуется решение за линейное время с константой дополнительной памяти.

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

Решение:
Несложно заметить следующее
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....

Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев

def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1

if left >= right:
return True # строка уже палиндром или можно удалить любой символ

# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))

@algoses

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

Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.

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

Решение:
Линейно пройдемся по элементам массива, поддерживая указатель на записываемый элемент. Затем удалим лишние индексы

def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]

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

@algoses

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

Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.

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

Решение:
Очевидно, что если в подпоследовательности будет больше двух положительных элементов, то x - y > x (x = max(x, y)) верно лишь в том случае, когда y < 0. Соответственно длина последовательности будет точно хотя бы равняться количеству отрицательных элементов. При построении последовательности возьмем один положительный элемент (потому что иначе с двумя положительными не будет выполняться условие |a_i - a_j| > max(a_i, a_j) и возьмем жадно аименьший положительный. Тогда можно будет проверить, получится ли этот положительный элемент добавить в последовательность отрицательных так чтобы не нарушалось то условие (для этого достаточно перебрать наименьшую абсолютную разницу, то есть просто перебрать пары соседних в отсортированном порядке).


int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;

@algoses

Задача с собеседования в лабораторию Т-банка

Задача:
Нам даны две последовательности A и B из 0 и 1 (длиной до 10^6). У вас есть две операции:
1. Выбрать последовательность и поменять местами элементы на позициях (i, j) - стоимость такой операции будет |i-j|
2. Выбрать элемент последовательности и поменять значение бита на противоположное, стоимость в таком случае будет 1
Требуется за минимальную стоимость сделать последовательности равными

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

Решение:
Заметим, что операцию 1 нет смысла использовать когда |i - j| > 1, а выигрышь стоимости в 1 достигается только при |i - j| = 1. Тогда можно решать задачу с помощью dp, dp_i - минимальный ответ для того чтобы сделать префиксы последовательностей длинной i равным.
Тогда пересчёта будет два:
Первый - это прийти в состояние i, воспользовавшись операцией 2 и тогда стоимость для префикса длины будет считаться как dp{i-1} + (a[i] != b[i])
Второй - это воспользоваться операцией 2 и поменять символы на позициях (i - 1, i), но в таком случае нужно проверить, что строки станут равными после этой операции (если быть точнее, то префиксы строк).

int n;
cin >> n;
string a, b;
cin >> a;
cin >> b;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + (a[i - 1] != b[i - 1]);
if (i >= 2 && a[i - 2] == b[i - 1] && a[i - 1] == b[i - 2]) {
dp[i] = min(dp[i], dp[i - 2] + 1);
}
}
cout << dp[n] << '\n';

@algoses

Задача с собеса Авито

На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.


Ограничения:
- длина строки от 1 до 5 * 10 ** 5
- строка состоит из английских букв в верхнем и нижнем регистре

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

Решение:
С помощью словаря подсчитаем частоты символов— O(N).Создадим массив корзин (bucket), где индекс — это частота символа.
(Максимальная возможная частота символа = N, если вся строка из одного символа.)
Разложим символы по корзинам в соответствии с их частотой — O(M), где M — число уникальных символов (M ≤ N). В конце пройдемся по корзине от самой высокой частоты к низкой и соберем результат — O(N)


def frequencySort(s):
    freq = {}
    for char in s:
         if chat not in freq:
              freq[char] = 0
        freq[char] += 1 
   

    buckets = [[] for _ in range(len(s) + 1)] 
    for char, count in freq.items():
        buckets[count].append(char) 
   
   
    result = []
    for count in range(len(buckets) - 1, -1, -1):
        for char in buckets[count]:
            result.append(char * count)
   
    return ''.join(result)

@algoses

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

Дан массив целых чисел nums и целое число k. Необходимо найти количество смежных подмассивов, произведение элементов которых строго меньше k.

nums = [10, 5, 2, 6], k = 100 
Ответ: 8 
Объяснение: 8 подмассивов удовлетворяют условию: 
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].

Ограничения:
длина от 1 до  3 *10^ 4
значения от 1 до 1000
k от 1 до 10 ^ 6

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

Решение:
Используем метод скользящего окна с двумя указателями (left и right). product = 1 (текущее произведение), count = 0 (счётчик подмассивов), left = 0 (левый указатель). Для каждого right от 0 до n-1. Умножаем product на nums[right]. Если product >= k, сдвигаем left, деля product на nums[left], пока product снова не станет < k. Добавляем к count количество новых подмассивов: right - left + 1.

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

@algoses

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

Задача 
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.

Чат алгоритмистов

Решение 
Найдем первое отличающееся вхождение, позицию i: a[i]!= a'[i](то есть самое левое) и найдем последнее (самое правое). Далее расширим эти границы: до тех пор, пока левее от левой границы в приведенном массиве a стоит меньше или равный a'[l-1]<= a'[l], будем двигать его влево. Аналогично и с правым указателем, расширим его вправо.

Код
l,r=-1,-1
for i in range(n):
  if a[i]!=aa[i]:
   r=i
   if l==-1:
    l=i
while l>0 and aa[l-1]<=aa[l]:
  l-=1
while r<n-1 and aa[r+1]>=aa[r]:
  r+=1
print(l+1,r+1)

@algoses

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

Дано бинарное дерево (не поиска):
struct Node {
Node* parent;
Node* left;
Node* right;
}

Нужно написать функцию, которая для двух данных вершин будет возвращать их наименьшего (ближайшего) общего предка:

Node* lca(Node* a, Node* b);

Ограничения: память O(1)

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:
Считаем глубину для каждой вершины, потом идем двумя указателями вверх от вершин, пока они не встретятся. O(h) по времени, где h - высота дерева.
#include <unordered_map>

struct Node {
Node* parent;
Node* left;
Node* right;
};

std::unordered_map<Node*, int> depth_map;

void compute_depths(Node* node, int depth = 0) {
if (!node) return;
depth_map[node] = depth;
if (node->left) {
node->left->parent = node;
compute_depths(node->left, depth + 1);
}
if (node->right) {
node->right->parent = node;
compute_depths(node->right, depth + 1);
}
}

Node* lca(Node* a, Node* b) {
int da = depth_map[a];
int db = depth_map[b];

while (da > db) {
a = a->parent;
--da;
}
while (db > da) {
b = b->parent;
--db;
}

while (a != b) {
a = a->parent;
b = b->parent;
}

return a;
}

@algoses

Один день из жизни стажера-аналитика в Т-банке

Выпускника прошлых потоков наших продвинутых курсов, на которые идут последние часы 50% скидки, не упусти свой шанс забрать разбор Т-банка и уже осенью получить заветный оффер.

Мой рабочий день начинается с планирования. Первым делом я проверяю календарь и список задач. Сегодня запланирована важная встреча с наставником, так что я принимаю решение поехать в офис — там коммуникация с командой эффективнее. Офис Т-банка расположен в центре Москвы, на Белорусской, что очень удобно: рядом сразу две станции метро и ветки МЦД.

Обычно, когда езжу в офис, я начинаю день с зала. Для сотрудников здесь доступен полноценный клуб с тренажерным залом, там есть всё и кардио, и все популярные тренажеры, и залы для групповых занятий. После тренировки сходил в баню и с отличным настроением пошел, встретился коллег-стажеров с нашего потока - мы обсудили подготовку к предстоящему ИТ-пикнику.

К 11:00 я уже сел за свое рабочее место. Изучил бэклог и расставляю приоритеты на день. Моя главная цель на стажировке - выполнить все задачи для последующего перевода в штат. Сегодня в фокусе - продолжение работы над ML-моделью для классификации клиентов из сегмента малого и среднего бизнеса. Это нужно для автоматизации работы с бизнесами и выявления некорректной регистрации бизнесов. После приоритизации задач, заглянул в кофе поинт позавтракать. Здесь всегда есть кофе, чай, свежие фрукты и выпечка. Это хорошая возможность на несколько минут переключиться и пообщаться с коллегами из других отделов. Затем наконец сел за решение задачи, покопался в подборе параметров модели для разметки бизнесов, получилось улучшить скор и сел дописывать тест в другой задаче, там были проблемы с мощностью теста и бадди посоветовал использовать cuped.

Около 13:00 отправляюсь в столовую. Для сотрудников организовано полноценное бесплатное питание (шведский стол). Выбрал котлеты, гречку, крем-суп и салат с моцареллой. Как мне кажется система бесплатной столовой получше решение, чем 1000 рублей в день на рестораны (еды значительно больше, ну и столовая в т-банке вкуснее).

В 13:30 у меня созвон с наставником. Мы проводили еженедельную оценку работы, проделанной на стажировке, он дает мне советы: я докладываю о прогрессе по модели, обсуждаю проблемные места и получаю обратную связь. Наставник отмечает, что я успешно справился с предыдущей задачей по классификации, и ставит новую - с дизайном АБ.

Вторая половина дня уходит на подготовку и запуск A/B-теста для нового сценария взаимодействия с клиентами малого бизнеса. Мне нужно проверить гипотезу, что измененная механика отправки email-уведомлений увеличит конверсию в отклик. В начале сегментировал клиентскую базу и сформировао тестовую и контрольную группы. Особое внимание уделяю исключению пересечений с другими текущими экспериментами в банке. К концу дня мне удается подготовить код для запуска теста, но дашборд сделать не успел.

В 17:30 рабочий день кончился и пошёл перед уходом поиграл с товарищем в настольный теннис.

@postypashki_old

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

Дан массив prices, где prices[i] — цена акции в день i. Нужно выбрать один день для покупки и позже другой день для продажи так, чтобы прибыль была максимальна. Если прибыли получить нельзя — вернуть 0.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:

Проходим массив один раз, поддерживая:
min_price — минимальную цену, встреченную слева (лучшая покупка до текущего дня);
best — максимальную прибыль на данный момент.
На каждом шаге обновляем best = max(best, prices[i] - min_price) и затем min_price = min(min_price, prices[i]).
Это даёт O(n) по времени и O(1) по памяти.

Код:

#include <bits/stdc++.h>
using namespace std;

int maxProfit(const vector<int>& prices) {
int min_price = INT_MAX;
int best = 0;
for (int p : prices) {
if (p > min_price) {
best = max(best, p - min_price);
}
min_price = min(min_price, p);
}
return best;
}

@algoses

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

Дана скобочная грамматика: в круглых скобках записано выражение, следом за ними идут квадратные скобки с неотрицательным целым числом. Разворачивается в виде конкатенации строки в круглых скобках на саму себя N раз, где N - число в квадратных скобках

Чуть более формально, грамматика -
term ::= a-z*
term ::= (term)[\d+]
term ::= term1term2 - разворачивается в конкатенацию двух выражений

На вход подается строка со скобочным выражением. Необходимо развернуть его в строку и вернуть. Предлагается считать, что скобочная последовательность на входе всегда корректна

Примеры:
"ab" -> "ab"
"(ab)[3]" -> "ababab"
"((ab)[2])[2]" -> "abababab"
"(a)[2](b)[2]" -> "aabb"
"()[1]bc" -> "bc"

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

Решение:
Аккуратная рекурсия

def parse_expression(s: str) -> str:
def helper(i):
res = ""
while i < len(s):
if s[i] == '(':
# Рекурсивно разбираем внутреннее выражение
inner, i = helper(i + 1)
# После этого должен идти [
assert s[i] == '[', f"Ожидалась [ на позиции {i}, а найдено {s[i]}"
i += 1
num_start = i
while s[i].isdigit():
i += 1
repeat = int(s[num_start:i])
assert s[i] == ']', f"Ожидалась ] на позиции {i}, а найдено {s[i]}"
i += 1
res += inner * repeat
elif s[i] == ')':
return res, i + 1
else:
res += s[i]
i += 1
return res, i

result, _ = helper(0)
return result

Подводные камни:
1) выход за границы строки при разборе, неточное вычленение содержимого подвыражений в скобках
2) остаются куски грамматики в выводе
3) некорректно парсится число в квадратных скобках, если имеет более одного разряда - например, парсится задом наперед или только один разряд

@algoses

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

Дана следующая структура мероприятий, имеющих временное начало и конец

struct Meeting {
    long long from;
    long long to;
}

vector<Meeting> crossing(const vector<Meeting>& meetings) ...

Необходимо найти пересекающиеся встречи

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

Решение:
Сортируем встречи по времени начала, затем проходим слева направо, поддерживая наибольший правый конец max_end среди уже просмотренных интервалов и индекс того интервала, который даёт max_end. Если следующий интервал начинается раньше max_end, то он пересекается с каким-то предыдущим (в частности — с тем, чьё max_end), помечаем оба как пересекающиеся. В конце возвращаем (или выводим) все исходные встречи, помеченные как пересекающиеся.

Код:
vector<Meeting> crossing(const vector<Meeting>& meetings) {
int n = (int)meetings.size();
if (n == 0) return {};

// Соберём (from, to, orig_index) и отсортируем по from
struct Node { long long from, to; int idx; };
vector<Node> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back({meetings[i].from, meetings[i].to, i});
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
if (a.from != b.from) return a.from < b.from;
return a.to < b.to;
});

vector<char> overlapped(n, 0); // пометки для исходных индексов

long long max_end = v[0].to;
int idx_max_sorted = 0; // индекс в v, который даёт max_end

// Считаем, что пересечение происходит если start < max_end (строгое пересечение).
// Если нужно считать касание по границе пересечением, менять на <= .
for (int i = 1; i < n; ++i) {
if (v[i].from < max_end) {
// v[i] пересекается с тем, у кого max_end
overlapped[v[i].idx] = 1;
overlapped[v[idx_max_sorted].idx] = 1;
}
if (v[i].to > max_end) {
max_end = v[i].to;
idx_max_sorted = i;
}
}

// Собираем результат в исходном порядке
vector<Meeting> res;
for (int i = 0; i < n; ++i) {
if (overlapped[i]) res.push_back(meetings[i]);
}
return res;
}

Время O(NlogN), память O(N)

@algoses

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

Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __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