![Data Structures & Algorithms Tutorial](https://www.tutorialspoint.com/data_structures_algorithms/images/data-structure-mini-logo.jpg)
- Data Structures & Algorithms
- DSA - Home
- DSA - Overview
- DSA - Environment Setup
- Algorithm
- DSA - Algorithms Basics
- DSA - Asymptotic Analysis
- DSA - Greedy Algorithms
- DSA - Divide and Conquer
- DSA - Dynamic Programming
- Data Structures
- DSA - Data Structure Basics
- DSA - Data Structures and Types
- DSA - Array Data Structure
- Linked Lists
- DSA - Linked List Basics
- DSA - Doubly Linked List
- DSA - Circular Linked List
- Stack & Queue
- DSA - Stack
- DSA - Expression Parsing
- DSA - Queue
- Searching Techniques
- DSA - Linear Search
- DSA - Binary Search
- DSA - Interpolation Search
- DSA - Hash Table
- Sorting Techniques
- DSA - Sorting Algorithms
- DSA - Bubble Sort
- DSA - Insertion Sort
- DSA - Selection Sort
- DSA - Merge Sort
- DSA - Shell Sort
- DSA - Quick Sort
- Graph Data Structure
- DSA - Graph Data Structure
- DSA - Depth First Traversal
- DSA - Breadth First Traversal
- Tree Data Structure
- DSA - Tree Data Structure
- DSA - Tree Traversal
- DSA - Binary Search Tree
- DSA - AVL Tree
- DSA - Red Black Trees
- DSA - B Trees
- DSA - B+ Trees
- DSA - Splay Trees
- DSA - Spanning Tree
- DSA - Tries
- DSA - Heap
- Recursion
- DSA - Recursion Basics
- DSA - Tower of Hanoi
- DSA - Fibonacci Series
- DSA Useful Resources
- DSA - Questions and Answers
- DSA - Quick Guide
- DSA - Useful Resources
- DSA - Discussion
C++ Program for Left Rotation and Right Rotation of a String
Rotation means we have to shift each character forward or backward direction. In the case of forward, the last character is forwarded to the index 0 also known as right rotation. In the case of backward first character at index 0 is backward to the last index also known as left rotation.
In this problem, we have given a string of characters and integer d. Our task is to print the left rotated string or right rotated string by d integer.
Only the permutation of the current string changes, not the length or frequency of the characters in the given string. Here d is less than the size of the string.
Let's see the examples−
Input 1
str = "HelloWorld", d = 5
Output 1
Left Rotation = "WorldHello" Right Rotation = "WorldHello"
Explanation:Here the both Left and Right rotation of the string is same because the total character present in the string is 10 and we have rotated both left and right by 5 characters.
Input 2
str = "abcdefgh", k = 3
Output 2
Left Rotation = "defghabc" Right Rotation = "fghabcde"
Explanation:Here we have rotated both left and right by 3 characters.
Approaches
We have seen the example above for the given string and integer, let us move to the approaches:
Approach 1: Reverse Method
The idea of this approach is simple. Rotated the string using the reverse method. For the left rotation first, reversed the starting d character as from index 0 to d of the string then reversed the remaining character (after the d character to the last index of the string). In the end, reversed the whole string and got the left rotated string.
For the right rotation, just need to pass the string and size of the string minus d to the forLeftRotation function to rotate it left by the size of the string minus d.
Example
#include <bits/stdc++.h> using namespace std; // Rotates string 'str' by d to the left. void forLeftRotation(string &str, int d){ reverse(str.begin(), str.begin()+d); reverse(str.begin()+d, str.end()); reverse(str.begin(), str.end()); } // Rotates string 'str' by d to the right. void forRightRotation(string &str, int d){ int n = str.size(); int newD = n - d; forLeftRotation(str, newD); } int main(){ string str = "HelloWorld!"; //given string int d = 5; //given integer string strL = str; //Call the function to rotate the string toward the left forLeftRotation(strL, d); cout << "Left Rotation is "<< strL << endl; string strR = str; //Call the function to rotate the string toward the right forRightRotation(strR, d); cout << "Right Rotation is "<< strR << endl; return 0; }
Output
Left Rotation is World!Hello Right Rotation is orld!HelloW
Note
As we saw in the previous section, the rotation occurs after the length of the string has been repeated and can be calculated by getting the mode of the current number with the given length of the string. In the program above, we are given the 'd' or the number of rotations less than the size of the string, and if the d is greater than the size of the string then the above code will give the error. But to be on the safe side, we can always do this −
d = d % (str.size())
Time and Space Complexity
The time complexity is O(N), Here N represent the size of the string.
The space complexity is O(1) as there is no extra space used, just storing the one string into the another, that space is used for an answer, so no extra space is used.
Approach 2: Using Extended String
The idea is that to rotate a string, we can use an extended string, which is twice as long as a regular string. Use the extended string for left rotation from index (d) to (length of string + d). And for the right rotation, pass the given string to forLeftRotation function to rotate the string left by the size of the string minus d.
Example
#include<bits/stdc++.h> using namespace std; // Rotates string 'str' by d to the left using extended string string forLeftRotation(string str, int d){ string temp = str + str; // extended string int idx = str.size(); //constructing a new rotated string's index string leftFirst = temp.substr(d, idx); return leftFirst; } // Rotates string 'str' by d to the right string forRightRotation(string str, int d){ return forLeftRotation(str, str.size() - d); } int main(){ string str = "HelloWorld!"; //given input int d = 5; //given integer // Call the function to rotate the string toward the left string strL = forLeftRotation(str, d); cout << "Left Rotation is "<< strL << endl; //Call the function to rotate the string toward the right string strR = forRightRotation(str, d); cout << "Right Rotation is "<< strR << endl; return 0; }
Output
Left Rotation is World!Hello Right Rotation is orld!HelloW
Note
As we already discussed above, in this program has the same scenario the given 'd' or the number of rotations is less than the size of the string, and if the d is greater than the size of the string then the above code will give the error. But to be on the safe side, we can always do this
d = d % (str.size())
Conclusion
In this tutorial, we have implemented a program for the Left Rotation and Right Rotation of a String. We have implemented two approaches. One approach uses the reverse method with a time complexity of O(N) and space complexity of O(1). Another Approach uses an extended string method with a time complexity of O(N) and space complexity of O(N) where N is the size of the given string.
- Related Articles
- JavaScript Program for Left Rotation and Right Rotation of a String
- Java Program for Left Rotation and Right Rotation of a String
- JavaScript Program for Longest Subsequence of a Number having Same Left and Right Rotation
- C Program for Program for array rotation?
- Minimize characters to be changed to make the left and right rotation of a string same
- JavaScript Program for Reversal algorithm for right rotation of an array
- Java Program for Reversal algorithm for right rotation of an array
- Reversal Algorithm for Right Rotation of an Array using C++
- C++ Program to Perform Left Rotation on a Binary Search Tree
- C Program for Reversal algorithm for array rotation
- C++ Program to Perform Right Rotation on a Binary Search Tree
- Python Program for array rotation
- Java Program for array rotation
- Golang Program For Array Rotation
- C++ Program to get blocks position after right side rotation
![Tutorials Point](https://www.tutorialspoint.com/articles/images/tp-print-page-logo.png)