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?