Заменить все пробелы в строке «на месте»

Напишите метод, заменяющий все пробелы в строке символами %20 . Требуется реализовать алгоритм с заменой «на месте», т.е. без использования дополнительных структур данных. Можно считать, что длина строки позволяет сохранить дополнительные символы.

Разумеется, решить задачу можно с помощью методаreplace строки, но здесь явно требуется реализовать алгоритм самостоятельно.

Сложность задачи в требовании не использовать дополнительные структуры данных. Иначе, можно просто завести вторую строчку и последовательно копировать все символы из первой, заменив при этом пробелы — так нельзя.

Общий подход к таким задачам — изменять строку, начиная с конца и двигаться к началу. В конце строки можно организовать дополнительное пространство, в котором можно изменять символы и при этом не потерять информацию.

Общая идея алгоритма следующая:

• первым проходом подсчитать количество пробелов
• умножив это значение на 3, получаем количество дополнительных символов в строке
• вторым проходом, который осуществляется с конца строки, выполняется ее модификация: пробел заменяется, а другой символ просто копируется

Т.к. в JavaScript строки неизменяемые, то придется преобразовать строку к массиву и выполнять все манипуляции с ним.

Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.