Изменить порядок строки на половину символа

Это вопрос интервью.

Дана такая строка, как: 123456abcdef, состоящая из n / 2 целых чисел, за которыми следуют n / 2 символа. Измените порядок строки, чтобы она содержала как 1a2b3c4d5e6f. Алгоритм должен быть на месте.

Решение, которое я дал, было тривиальным - O (n ^ 2). Просто сдвиньте символы на n / 2 разряда влево.

Я пробовал использовать рекурсию как -
а. Поменяйте местами более позднюю половину первой половины с предыдущей половиной 2-й части - например,
123 456 abc def
123 abc 456 def
б. Рекурсия на две половины.

Я застрял в том, что подкачка зависит от количества элементов - например.

Что делать дальше? 123 abc 12ab 3c

А что делать для: 12345 abcde 123abc 45ab

Это довольно старый вопрос, возможно, он дублируется. Пожалуйста, дайте мне знать .. :)

Другой пример: Вход: 38726zfgsa Вывод: 3z8f7g2s6a