Given a string of size n, write functions to perform the following operations on a string-
- Left (Or anticlockwise) rotate the given string by d elements (where d <= n)
- Right (Or clockwise) rotate the given string by d elements (where d <= n).
Examples:
Input : s = "neveropen"
d = 2
Output : Left Rotation : "eksforGeeksGe"
Right Rotation : "ksGeeksforGee"
Input : s = "qwertyu"
d = 2
Output : Left rotation : "ertyuqw"
Right rotation : "yuqwert"
Method 1:
A Simple Solution is to use a temporary string to do rotations. For left rotation, first, copy last n-d characters, then copy first d characters in order to the temporary string. For right rotation, first, copy last d characters, then copy n-d characters.
Can we do both rotations in-place and O(n) time?
The idea is based on a reversal algorithm for rotation.
// Left rotate string s by d (Assuming d <= n) leftRotate(s, d) reverse(s, 0, d-1); // Reverse substring s[0..d-1] reverse(s, d, n-1); // Reverse substring s[d..n-1] reverse(s, 0, n-1); // Reverse whole string. // Right rotate string s by d (Assuming d <= n) rightRotate(s, d) // We can also call above reverse steps // with d = n-d. leftRotate(s, n-d)
Below is the implementation of the above steps :
C++
// C program for Left Rotation and Right// Rotation of a String#include<bits/stdc++.h>using namespace std;// In-place rotates s towards left by dvoid leftrotate(string &s, int d){ reverse(s.begin(), s.begin()+d); reverse(s.begin()+d, s.end()); reverse(s.begin(), s.end());}// In-place rotates s towards right by dvoid rightrotate(string &s, int d){ leftrotate(s, s.length()-d);}// Driver codeint main(){ string str1 = "neveropen"; leftrotate(str1, 2); cout << str1 << endl; string str2 = "neveropen"; rightrotate(str2, 2); cout << str2 << endl; return 0;} |
Output:
Left rotation: eksforGeeksGe Right rotation: ksGeeksforGee
Time Complexity: O(N), as we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(1), as we are not using any extra space.
Method 2:
We can use extended string which is double in size of normal string to rotate string. For left rotation, access the extended string from index n to the index len(string) + n. For right rotation, rotate the string left with size-d places.
Approach:
The approach is
// Left rotate string s by d leftRotate(s, n) temp = s + s; // extended string l1 = s.length // length of string return temp[n : l1+n] //return rotated string. // Right rotate string s by n rightRotate(s, n) // We can also call above reverse steps // with x = s.length - n. leftRotate(s, x-n)
Below is implementation of above approach
C++
// C++ program for Left Rotation and Right// Rotation of a String#include <bits/stdc++.h>using namespace std;// Rotating the string using extended stringstring leftrotate(string str1, int n){ // creating extended string and index for new rotated // string string temp = str1 + str1; int l1 = str1.size(); string Lfirst = temp.substr(n, l1); // now returning string return Lfirst;}// Rotating the string using extended stringstring rightrotate(string str1, int n){ return leftrotate(str1, str1.size() - n);}// Driver codeint main(){ string str1 = leftrotate("neveropen", 2); cout << str1 << endl; string str2 = rightrotate("neveropen", 2); cout << str2 << endl; return 0;}// This code is contributed by Susobhan Akhuli |
eksforGeeksGe ksGeeksforGee
Time Complexity: O(N), where N is the size of the given string.
Auxiliary Space: O(N)
Method 3:
This approach defines two functions for left and right rotation of a string using the rotate() function provided by the STL (Standard Template Library) in C++. The left_rotate_string() function rotates the string s by d positions to the left, while the right_rotate_string() function rotates the string s by d positions to the right. Both functions return the rotated string.
Approach:
The approach is
- Define two functions: left_rotate_string() and right_rotate_string().
- In left_rotate_string(), perform a left rotation on the string s by d elements using the rotate() function.
- In right_rotate_string(), perform a right rotation on the string s by d elements using the rotate() function.
- Return the rotated string.
Below is the implementation of the above approach:
C++
// CPP program for Left Rotation and Right// Rotation of a String#include <algorithm>#include <iostream>using namespace std;// Define the left_rotate_string functionstring left_rotate_string(string s, int d){ // Perform a left rotation on the string by d elements rotate(s.begin(), s.begin() + d, s.end()); return s;}// Define the right_rotate_string functionstring right_rotate_string(string s, int d){ // Perform a right rotation on the string by d elements rotate(s.rbegin(), s.rbegin() + d, s.rend()); return s;}int main(){ string s = "neveropen"; int d = 2; cout << "Left Rotation: " << left_rotate_string(s, d) << endl; cout << "Right Rotation: " << right_rotate_string(s, d) << endl; s = "qwertyu"; d = 2; cout << "Left Rotation: " << left_rotate_string(s, d) << endl; cout << "Right Rotation: " << right_rotate_string(s, d) << endl; return 0;}// This code is contributed by Susobhan Akhuli |
Left Rotation: eksforGeeksGe Right Rotation: ksGeeksforGee Left Rotation: ertyuqw Right Rotation: yuqwert
Time complexity: O(n), where n is the length of the input string s. This is because the rotation operation requires visiting every character in the string exactly once.
Auxiliary Space: O(n)
Please refer complete article on Left Rotation and Right Rotation of a String for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
