## Sunday, April 13, 2014

### Efficiently Right Shift a String

You are given a string and a number k. You need to right shift the string k times. What is the efficient way to solve this?

Example:
the string is "Democracy".
If k is 2, then the output should be "cyDemocra".
If k is 3, then the output should be "acyDemocr"

O(nk) time complexity, O(1) space complexity.

where n is the length of the string.

Right shift the string k times.

```main()
{
char s[] = "Some string ....";
int n = streln(s);

for(int i=0; i<k; i++)
rightShift(s, n);
}

rightShift(char s[], int length)
{
char temp = s[length-1];
for(int i=length-1; i>0; i--)
s[i]=s[i-1];
s[0] = temp;
}
```

O(n) time complexity, and O(k) space complexity

```char s[] = "Some string ....";
int n = streln(s);
char *exsp = (char*)calloc(k, sizeof(char));

for(int i=0; i<k; i++)
exsp[i]=s[n-k+i];

for(int i=n-1; i>=k; i--)
s[i]=s[i-k];

for(int i=0; i<k; i++)
s[i]=exsp[i];
```

O(n) time complexity, O(1) space complexity

Reverse the entire array.
Reverse the array from 0 to k-1, and from k-1 to n-1.

```Reverse(char s[], int start, int end)
{
for(int i=start, j=end; i<j; i++, j--)
{
int t=s[i];
s[i]=s[j];
s[j]=t;
}
}

Reverse(s, 0, n-1);
Reverse(s, 0, k-1);
Reverse(s, k, n-1);
```