Transform string from a1b2c3d4 to abcd1234

Question

I am given a string which has numbers and letters.Numbers occupy all odd positions and letters even positions.I need to transform this string such that all letters move to front of array,and all numbers at the end.

The relative order of the letters and numbers needs to be preserved

I need to do this in O(n) time and O(1) space.

eg: a1b2c3d4 -> abcd1234 , x3y4z6 -> xyz346

This previous question has an explanation algorithm, but no matter how hard i try,i cant get a hold of it.

I hope someone can explain me this with a example test case .

Answer 1

The key is to think of the input array as a matrix like this:

a 1
b 2
c 3
d 4

and realize that you want the transpose of this matrix

a b c d
1 2 3 4

Remember, multi-dimensional arrays are really just single-dimensional arrays in disguise so you can do this. But you need to do this in-place to satisfy the O(1) space requirement. Fortunately, this is a well-known problem complete with several possible approaches.