You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 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
}
``````
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.