Пока курил придумал решение за константное время О(1) и без доп памяти(ну почти).
Если реализовать строку как двусвязный список котором есть указатель на первый, последний элемент и булево значение для определение направления реверса.
А в узле списка храним значение(тут можно уточнить кодировку и т.д.) и указатели a,b на соседние елементы.
Правда если алгоритм используется один раз то нет выигрыша, т.к. нужно перевести строку из «стандартной» реализации в «новую» структуру данных. Но если такая задача встречается много раз для каждой строки (и строки большие), то сэкономил вам кучу денег на серверном времени))
Если реализовать строку как двусвязный список котором есть указатель на первый, последний элемент и булево значение для определение направления реверса.
А в узле списка храним значение(тут можно уточнить кодировку и т.д.) и указатели a,b на соседние елементы.
Правда если алгоритм используется один раз то нет выигрыша, т.к. нужно перевести строку из «стандартной» реализации в «новую» структуру данных. Но если такая задача встречается много раз для каждой строки (и строки большие), то сэкономил вам кучу денег на серверном времени))