1

I encountered a simple (as I thought) exercise of rotating string:

To rotate string by K characters means to cut these characters from the beginning and transfer them to the end. If K is negative, characters, on contrary should be transferred from the end to the beginning.

I at once invented solution which uses concatenation of two substrings. However, I found the following addition:

if you want more serious challenge, you are encouraged to perform rotation "in-place"

task is from here - be sure it is not my college assignment etc

I could not see any simple way to do this (I suppose there should be O(N) algorithm). If I copy 0-th char to temporary variable and copy K-th char to its place, then 2K-th char to the place of K-th etc. - I will succeed provided that K and string length are co-prime. I think I can manage with other Ks adding outer loop to repeat the process from 1-th char, then 2-th etc - I think up to GCD(K, strlen(S))

But it looks too clumsy.

Alumashka
  • 195
  • 1
  • 6
  • Do you want O(n) space complexity (n strings in memory) or O(n) time complexity (one operation per character, essentially), or both? – cyphar Oct 11 '13 at 10:54
  • By "in-place" I mean O(1) space complexity so O(N) is about time complexity of course. Thanks for your clarification! – Alumashka Oct 11 '13 at 10:55
  • 1
    Possible duplicate of [Algorithm to rotate an array in linear time](http://stackoverflow.com/questions/4457277/algorithm-to-rotate-an-array-in-linear-time) – Bernhard Barker Oct 11 '13 at 11:06

1 Answers1

6

Let's look at rotating it by 6 characters:

Original: 123456789
Desired:  789 123456

Now look what happens when we reverse both parts of the desired string:

987 654321

This is just the reverse of the original string.

So, what we need to do is first reverse the string, then reverse both parts.

It's easy to reverse a string in linear time in-place.

This is a duplicate of another question very recently asked, answering it seems like less effort than finding the duplicate - I'll just make this community wiki.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • Oh, I see now. That is really cool, thanks! I think, in other words we can reverse string twice - first time about its center and second time about `center + K/2` - I'll check this... – Alumashka Oct 11 '13 at 11:07