Right shift N characters

"abc", 4 -> "cab"

Solution: I love yahoo trick

When mirroring the order of chunks without changing the order of said chucks, I love Yahoo is a great trick

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

Ex: I love yahoo -> yahoo love I

step 1: reverse whole string

oohay evol I

step 2: reverse each word

yahoo love I

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

public class Solution {

  private void reverse(char[] array, int left, int right) {
    while (right > left){
      char tmp = array[right];
      array[right] = array[left];
      array[left] = tmp;
      right--;
      left++;
    }
  }

  public String rightShift(String input, int n) {
    if (input.length() <= 1) return input;

    char[] array = input.toCharArray();
    n %= array.length; //how many steps forward
    
    //reverse 0 -> len - n - 1
    //reverse n -> last element
    //reverse everything

    reverse(array, 0, array.length - n - 1);
    reverse(array, array.length - n , array.length - 1);
    reverse(array, 0, array.length - 1);

    return new String(array);
        
  }
}

Special case to watch for:

When N is at the center, reverse(0,N - 1) + reverse(N, length) will overshoot by one.

Thus to mitigate the issue its changed to reverse(0, length - n - 1) reverse(length - n, length)

Example: a b c d e f g n = 3

0 1 2 3 4 5 6

n - 1 = 2 will swap to 4

Length - n - 1:

Odd case: 7-3-1 = 3

Even case: 6 - 3 - 1 = 2

Time Comp: O(2N) two traversals

Space Comp: O(N) char array

Last updated

Was this helpful?