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"






Answer 1:

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;
}

Answer 2:

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];

Answer 3:

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);

2 comments:

  1. Answer 3 is not O(n) time complexity but O(n^2) time complexity

    ReplyDelete
  2. How is it O(n^2) time complexity? The for loop executes at max n iterations only. So, it is O(n) only.

    ReplyDelete