Interview Practice 26 – String Right-rotation


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”.


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.

defghijbca  <- p1 doesn't move since it reaches the end
#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;

// 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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: