You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Right-rotate String

Nicholas Wong
Nicholas Wong

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.