0

Cyclic left shift a given string for N position, say cyclic left shift "abcXYZdef" for 3 positions, to get "XYZdefabc".

Here I provide 2 solutions:

  1. left shift the string for 1 position, and do this for N times.
  2. concatenate two strings into one and return the specific substring as the result.

The question is: Is it possible to implement such an algorithm in O(N) time and O(1) space?

YSC
  • 38,212
  • 9
  • 96
  • 149
JohnSnow
  • 3
  • 2
  • `left shift the string for 1 position, and do this for N times` So how would you implement that? What do you think the complexity of such algorithm would be? – KamilCuk Jun 08 '20 at 07:54
  • How do you imagine space O(N) algo with O(1) time? Just initialization of memory takes O(N) – MBo Jun 08 '20 at 07:55
  • 2
    There is a mismatch of stated time and space complexities in the heading and the body. – Eugene Ryabtsev Jun 08 '20 at 07:58
  • 1
    @darune: O(1) space means here: the rotating algorithm needs an extra bunch of space of constant size (does not depend on the size of the string to rotate). – YSC Jun 08 '20 at 08:25
  • @KamilCuk The implementation is as straightforward as the statement itself. I think the time complexity would be O(K*N) when shifting K times? – JohnSnow Jun 08 '20 at 08:41
  • @PaulHankin I think this answer is O(1) space O(N) time, am I right?https://stackoverflow.com/a/4457397/6350731 – JohnSnow Jun 08 '20 at 08:41

1 Answers1

0

This is a theoretic problem more than a practical one. Your problem is O(N) time and O(1) space constraint.

O(1) space constraint means no dynamic allocation (even how small you want it to be). This means we cannot have a buffer for the to be rotated chars and we cannot copy the string input either. We could have a buffer for 1 char for example (constant allocation) and then rotate one step M times - but rotating just one time is already O(N). While we may iterate/rotate as many times we like, it must be a constant number of times and not depending on the input or otherwise it ends up being O(N*M).

So what if we rotate single chars more than one step at a time (eg. say we need to rotate 3 places) ? - this could lead to a something that might satisfy the requirement. But then how to track what has been rotated (remember we cannot make a buffer the size of the number of steps to rotate - only constant size).

Maybe this conundrum can be solved, but it needs some clever trick to pull off the way I understand it, mathematical or otherwise.

darune
  • 10,480
  • 2
  • 24
  • 62