Можно сделать данную операцию не за O(n), а за O(log n), используя декартово дерево по неявному ключу. Строить его нужно на символах данной строки. Построение - О(n*log(n)), зато удаление и вставка из произвольного места(в т.ч. удаление символа из начала и вставка в конец) за O(log(n).
