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 .
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With