## Interview Practice 26 – String Right-rotation

### 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(T): "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```
```#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
}```