Left And Right Rotation Of A String

Easy
0/40
Average time to solve is 15m
44 upvotes
Asked in companies
AmazonAmerican ExpressBajaj Electricals Ltd

Problem statement

You are given a string 'str' and an integer 'D'. Your task is to rotate the given string left (anticlockwise) and right (clockwise) by 'D' units from the starting index. You are required to return the rotated string.

Example :

Left-Right Rotation

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run.

Then the test cases follow:

The first line of each test case contains the string 'str'.

The second and last line of each test case contains an integer 'D', representing the number of units by which the string is to be rotated left or right.
Output format : 
For each test case, print the left and right rotations of the string separated by a single space.

Output for every test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.

1. leftRotate(): This function should return the string after left rotation.

2. rightRotate(): This function should return the string after right rotation.
Constraints : 
1 <= T <= 10
1 <= |str| <= 10^5
1 <= D <= 10^5
Where |str| denotes the length of the string str.

Time Limit: 1 sec
Sample Input 1 :
1
codingninjas
3
Sample Output 1 :
ingninjascod jascodingnin
Explanation For The Sample Output 1 :
In string “codingninjas” the substring of length 'D' = 3, starting from the beginning is “cod”, in the left rotation this substring is removed from the beginning and attached to the end of the string (i.e. anti-clockwise).

Similarly, in the right rotation, the substring of length 'D'  = 3 from the end is “jas”, this substring is removed from the end and attached to the beginning of the string(i.e. clockwise).
Sample Input 2 :
2
abcd
4
abc
4
Sample Output 2 :
abcd abcd
bca cab
Explanation For The Sample Output 2 :
In the first test case, as 'D' is equal to the length of the string so the substring same as the given string needs to be removed from the beginning and from the end and attached to the end and beginning of the empty string in the left and the right rotation respectively.

In the second test case, as 'D' is greater than the length of the string, so rotate it multiple times. After rotating the given string by '3' units, we get the same string as given, So now rotate the given string by 1 i.e('D' % 'N') units.
Hint

Try to think in terms of copying substrings into a new string.

Approaches (2)
Brute Force

The idea is to use an additional string to store the copies of required substrings. So we will Make initialize an empty string named ‘ANS’. 

 

  • For left rotation of given string, append last ‘N’ - ‘D’ characters to ‘ANS’, then append the remaining first ‘D’ characters to the ‘ANS’.
  • The required string after left rotation is ‘ANS’.
  • Return the current state of ‘ANS’.
  • For right rotation again initialize ans with an empty string (i.e. ‘ANS’ = “”) and append last ‘D’ characters of the given string to the ‘ANS’, then append the remaining ‘N’ - ‘D’ characters of the given string from beginning to the ans. Now the required string after right rotation is ‘ANS’.
  • Print the current state of ‘ANS’.

 

Explanation with an example: 

 

Let the given string = ”abcdef” , D = 2.

Initialize ‘ANS’ = ””, for left rotation: 

  • ‘ANS’ = “” + “cdef”. Now ‘ANS’ become equal to “cdef”
  • ‘ANS’ =  “cdef” + “ab”. Now ‘ANS’ become equal “cdefab” which is the expected result.

For right rotation again initialize ans to empty:

  • ‘ANS’ = “” + “ef”. Now ‘ANS’  become equal to “ef”.
  • ‘ANS’ = “ef” + “abcd”. Now ‘ANS’ become equal to “efabcd” which is the expected result.
Time Complexity

O(N) where N is the length of the string.

 

In the worst case, we have to traverse the whole string in each rotation. Hence the overall complexity will be O(N).

Space Complexity

O(N), where N is the length of the string.

 

In the worst case, as the temporary string is used to store the string after rotation is at least equal to the length of the string. Hence the overall complexity will be O(N).

Code Solution
(100% EXP penalty)
Left And Right Rotation Of A String
Full screen
Console