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

Написать метод, который заменит все пробелы в строке на '%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