Reorder a string by half the character

Question

This is an interview question.

Given a string such as: 123456abcdef consisting of n/2 integers followed by n/2 characters. Reorder the string to contain as 1a2b3c4d5e6f . The algortithm should be in-place.

The solution I gave was trivial - O(n^2). Just shift the characters by n/2 places to the left.

I tried using recursion as -
a. Swap later half of the first half with the previous half of the 2nd part - eg
123 456 abc def
123 abc 456 def
b. Recurse on the two halves.

The pbm I am stuck is that the swapping varies with the number of elements - for eg.

What to do next? 123 abc 12ab 3c

And what to do for : 12345 abcde 123abc 45ab

This is a pretty old question and may be a duplicate. Please let me know.. :)

Another example: Input: 38726zfgsa Output: 3z8f7g2s6a

Answer 1

Here's how I would approach the problem:

1) Divide the string into two partitions, number part and letter part
2) Divide each of those partitions into two more (equal sized)
3) Swap the second the third partition (inner number and inner letter)
4) Recurse on the original two partitions (with their newly swapped bits)
5) Stop when the partition has a size of 2

For example:

123456abcdef -> 123456 abcdef -> 123 456 abc def -> 123 abc 456 def

123abc -> 123 abc -> 12 3 ab c -> 12 ab 3 c

12 ab -> 1 2 a b -> 1 a 2 b

... etc

And the same for the other half of the recursion..

All can be done in place with the only gotcha being swapping partitions that aren't the same size (but it'll be off by one, so not difficult to handle).