Right-rotate String

Question

Write a program to right-rotate a string by m characters. Right-rotating a string means moving m characters at the left of string to the right. Is it required the time complexity is O(n) and helper memory size is O(1). For example, right-rotate “abcdefghi” by 3 characters gives “defghiabc”.

Solution

There are 2 ways to do it. The first one is that we divide the string into 2 parts (XY). X is the part to move to the right and Y is the one moving on to the left. Reverse them in place 2 times.

XY: "abcdefghi" 
R(X) R(Y): "cbaihgfed" 
YX: "defghiabc"

Secondly we can swap character one by one. Let p0 at position 0, p1 at position m. Swap their characters repeatedly with moving both pointer right by 1.

abcdefghij 
dbcaefghij 
decabfghij 
defabcghij 
defgbcahij 
defghcabij 
defghiabcj 
defghijbca <- p1 doesn't move since it reaches the end 
defghijacb 
defghijabc

Full example

#include <iostream> 

// reverse the string between start and end
void reverse_string(char * start_pointer, char * end_pointer) {
  while (start_pointer < end_pointer) {
    char temp_char = * start_pointer;* start_pointer = * end_pointer;* end_pointer = temp_char;
    start_pointer++;
    end_pointer--;
  }
} 

// solution 1 
void left_rotate_string_1(char * string_pointer, int n) {
  if (string_pointer == NULL) return;
  int length = strlen(string_pointer);
  if (n > length || n <= 0) return;
  char * first_start_pointer = string_pointer;
  char * first_end_pointer = string_pointer + n - 1;
  char * second_start_pointer = string_pointer + n;
  char * second_end_pointer = string_pointer + length - 1;
  reverse_string(first_start_pointer, first_end_pointer);
  reverse_string(second_start_pointer, second_end_pointer);
  reverse_string(first_start_pointer, second_end_pointer);
} 

// solution 2 
void left_rotate_string_2(char * string_pointer, int n) {
  if (string_pointer == NULL) return;
  int length = strlen(string_pointer);
  if (n > length || n <= 0) return;
  char * pointer_1 = string_pointer;
  char * pointer_2 = string_pointer + n;
  char * pointer_end = string_pointer + length - 1;
  while (pointer_1 != pointer_2) {
    char temp_char = * pointer_1;* pointer_1 = * pointer_2;* pointer_2 = temp_char;
    if (pointer_1 != pointer_end) pointer_1++;
    if (pointer_2 != pointer_end) pointer_2++;
  }
} 

// main 
int main() {
  char string_1[] = "abcdefghij";
  left_rotate_string_1(string_1, 3);
  printf("%sn", string_1); // defghijabc 
  char string_2[] = "abcdefghij";
  left_rotate_string_2(string_2, 3);
  printf("%sn", string_2); // defghijabc 
}