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;} |
Java
// Java program for Left Rotation and Right // Rotation of a String import java.util.*;import java.io.*;class GFG { // function that rotates s towards left by d static String leftrotate(String str, int d) { String ans = str.substring(d) + str.substring(0, d); return ans; } // function that rotates s towards right by d static String rightrotate(String str, int d) { return leftrotate(str, str.length() - d); } // Driver code public static void main(String args[]) { String str1 = "neveropen"; System.out.println(leftrotate(str1, 2)); String str2 = "neveropen"; System.out.println(rightrotate(str2, 2)); }}// This code is contributed by rachana soma |
Python3
# Python3 program for Left # Rotation and Right# Rotation of a String# In-place rotates s towards left by ddef leftrotate(s, d): tmp = s[d : ] + s[0 : d] return tmp # In-place rotates s # towards right by ddef rightrotate(s, d): return leftrotate(s, len(s) - d)# Driver codeif __name__=="__main__": str1 = "neveropen" print(leftrotate(str1, 2)) str2 = "neveropen" print(rightrotate(str2, 2))# This code is contributed by Rutvik_56 |
C#
// C# program for Left Rotation and Right // Rotation of a String using System; class GFG { // function that rotates s towards left by d static String leftrotate(String str, int d) { String ans = str.Substring(d,str.Length-d) + str.Substring(0, d); return ans; } // function that rotates s towards right by d static String rightrotate(String str, int d) { return leftrotate(str, str.Length - d); } // Driver code public static void Main(String []args) { String str1 = "neveropen"; Console.WriteLine(leftrotate(str1, 2)); String str2 = "neveropen"; Console.WriteLine(rightrotate(str2, 2)); }}/* This code is contributed by PrinciRaj1992 */ |
Javascript
<script>// JavaScript program for Left Rotation and Right// Rotation of a String// Function that rotates s towards left by dfunction leftrotate(str, d) { var ans = str.substring(d, str.length) + str.substring(0, d); return ans;}// Function that rotates s towards right by dfunction rightrotate(str, d){ return leftrotate(str, str.length - d);}// Driver codevar str1 = "neveropen";document.write(leftrotate(str1, 2) + "<br>");var str2 = "neveropen";document.write(rightrotate(str2, 2) + "<br>");// This code is contributed by rdtank</script> |
Output
eksforGeeksGe ksGeeksforGee
Time Complexity: O(N), where N is the size of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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.
The idea 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;} |
Java
// Java program for Left Rotation and Right// Rotation of a Stringimport java.io.*;import java.util.*;class GFG { // Rotating the string using extended string static String leftrotate(String str1, int n) { // creating extended string and index for new // rotated string String temp = str1 + str1; int l1 = str1.length(); String Lfirst = temp.substring(n, n + l1); // now returning string return Lfirst; } // Rotating the string using extended string static String rightrotate(String str1, int n) { return leftrotate(str1, str1.length() - n); } // Driver code public static void main(String args[]) { String str1 = "neveropen"; System.out.println(leftrotate(str1, 2)); String str2 = "neveropen"; System.out.println(rightrotate(str2, 2)); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Python3
# Python3 program for Left# Rotation and Right# Rotation of a Stringdef leftrotate(str1, n): # extended string temp = str1 + str1 l = len(str1) # Return string return temp[n :l+n]def rightrotate(str1, n): return leftrotate(str1, len(str1)-n) return temp[l-n : l1-n ]# Driver codeif __name__=="__main__": str1 = "neveropen" print(leftrotate(str1, 2)) str2 = "neveropen" print(rightrotate(str2, 2))# This code is contributed by sam snehil |
C#
// C# program for Left Rotation and Right// Rotation of a Stringusing System;class GFG { // Rotating the string using extended string static String leftrotate(String str1, int n) { // creating extended string and index for new // rotated string String temp = str1 + str1; int l1 = str1.Length; String Lfirst = temp.Substring(n, l1); // now returning string return Lfirst; } // Rotating the string using extended string static String rightrotate(String str1, int n) { return leftrotate(str1, str1.Length - n); } // Driver code public static void Main(String[] args) { String str1 = "neveropen"; Console.WriteLine(leftrotate(str1, 2)); String str2 = "neveropen"; Console.WriteLine(rightrotate(str2, 2)); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Javascript
// JavaScript program for Left Rotation and Right// Rotation of a String// Function that rotates string towards left by nfunction leftrotate(str1, n) { var temp = str1 + str1; var l1 = str1.length; var Lfirst = temp.substr(n,l1);// now returning string return Lfirst;}// Function that rotates string towards right by nfunction rightrotate(str, d){ return leftrotate(str, str.length - d);}// Driver codevar str1 = "neveropen";console.log(leftrotate(str1, 2));var str2 = "neveropen";console.log(rightrotate(str2, 2) );// This code is contributed by sam snehil |
Output
eksforGeeksGe ksGeeksforGee
Time Complexity: O(N), where N is the size of the given string.
Auxiliary Space: O(n), where N is the size of the given string.
This article is contributed by Aart_Rathi and Rishabh Jain. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Approach#3: Using deque
This approach defines two functions for left and right rotation of a string using the deque data structure from the collections module in Python. 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.
Algorithm
1. Define two functions for left rotation and right rotation.
2. Convert the input string to a deque using the collections module.
3. To perform left rotation, use the rotate() method with a negative rotation point.
4. To perform right rotation, use the rotate() method with a positive rotation point.
5. Convert the deque back to a string using the join() method.
6. Return the rotated string.
C++
#include <bits/stdc++.h>using namespace std;// Nikunj Sonigarastring leftRotateString(string s, int d) { deque<char> charDeque(s.begin(), s.end()); rotate(charDeque.begin(), charDeque.begin() + d, charDeque.end()); return string(charDeque.begin(), charDeque.end());}string rightRotateString(string s, int d) { deque<char> charDeque(s.begin(), s.end()); rotate(charDeque.rbegin(), charDeque.rbegin() + d, charDeque.rend()); return string(charDeque.begin(), charDeque.end());}int main() { string s = "neveropen"; int d = 2; cout << "Left Rotation: " << leftRotateString(s, d) << endl; cout << "Right Rotation: " << rightRotateString(s, d) << endl; s = "qwertyu"; d = 2; cout << "Left Rotation: " << leftRotateString(s, d) << endl; cout << "Right Rotation: " << rightRotateString(s, d) << endl; return 0;} |
Java
import java.io.*;import java.util.ArrayDeque;import java.util.Deque;public class GFG { // Function to left rotate a string by // 'd' positions public static String leftRotateString(String s, int d) { // Create a deque and initialize it with // the characters from the input string Deque<Character> charDeque = new ArrayDeque<>(); for (char c : s.toCharArray()) { charDeque.addLast(c); } // Perform left rotation by 'd' positions for (int i = 0; i < d; i++) { char firstChar = charDeque.removeFirst(); charDeque.addLast(firstChar); } // Convert the deque back to a string and return it StringBuilder result = new StringBuilder(); for (char c : charDeque) { result.append(c); } return result.toString(); } // Function to right rotate a string by // 'd' positions public static String rightRotateString(String s, int d) { // Create a deque and initialize it with // the characters from the input string Deque<Character> charDeque = new ArrayDeque<>(); for (char c : s.toCharArray()) { charDeque.addLast(c); } // Perform right rotation by 'd' positions for (int i = 0; i < d; i++) { char lastChar = charDeque.removeLast(); charDeque.addFirst(lastChar); } // Convert the deque back to a string and return it StringBuilder result = new StringBuilder(); for (char c : charDeque) { result.append(c); } return result.toString(); } public static void main(String[] args) { String s = "neveropen"; int d = 2; System.out.println("Left Rotation: " + leftRotateString(s, d)); System.out.println("Right Rotation: " + rightRotateString(s, d)); s = "qwertyu"; d = 2; System.out.println("Left Rotation: " + leftRotateString(s, d)); System.out.println("Right Rotation: " + rightRotateString(s, d)); }} |
Python3
from collections import dequedef left_rotate_string(s, d): char_deque = deque(s) char_deque.rotate(-d) return ''.join(char_deque)def right_rotate_string(s, d): char_deque = deque(s) char_deque.rotate(d) return ''.join(char_deque)s = "neveropen"d = 2print("Left Rotation:", left_rotate_string(s, d))print("Right Rotation:", right_rotate_string(s, d))s = "qwertyu"d = 2print("Left Rotation:", left_rotate_string(s, d))print("Right Rotation:", right_rotate_string(s, d)) |
C#
using System;using System.Collections.Generic;class Program{ // Nikunj Sonigara // Function to left rotate a string by 'd' positions static string LeftRotateString(string s, int d) { // Convert the input string to a deque of characters Queue<char> charQueue = new Queue<char>(s); // Rotate the deque to the left by 'd' positions for (int i = 0; i < d; i++) { char firstChar = charQueue.Dequeue(); charQueue.Enqueue(firstChar); } // Convert the deque back to a string and return it return new string(charQueue.ToArray()); } // Function to right rotate a string by 'd' positions static string RightRotateString(string s, int d) { // Convert the input string to a deque of characters Queue<char> charQueue = new Queue<char>(s); // Calculate the number of positions to rotate to the right int rotateCount = s.Length - d; // Rotate the deque to the right by 'rotateCount' positions for (int i = 0; i < rotateCount; i++) { char lastChar = charQueue.Dequeue(); charQueue.Enqueue(lastChar); } // Convert the deque back to a string and return it return new string(charQueue.ToArray()); } static void Main() { string s = "neveropen"; int d = 2; Console.WriteLine("Left Rotation: " + LeftRotateString(s, d)); Console.WriteLine("Right Rotation: " + RightRotateString(s, d)); s = "qwertyu"; d = 2; Console.WriteLine("Left Rotation: " + LeftRotateString(s, d)); Console.WriteLine("Right Rotation: " + RightRotateString(s, d)); }} |
Javascript
// Define the left_rotate_string function in JavaScriptfunction left_rotate_string(s, d){ // Create a deque object and add each character of the string to it let char_deque = [...s]; // Perform a left rotation on the deque object by rotating it by -d elements char_deque = char_deque.slice(d).concat(char_deque.slice(0, d)); // Convert the deque object back to a string and return it return char_deque.join('');}// Define the right_rotate_string function in JavaScriptfunction right_rotate_string(s, d){ // Create a deque object and add each character of the string to it let char_deque = [...s]; // Perform a right rotation on the deque object by rotating it by d elements char_deque = char_deque.slice(-d).concat(char_deque.slice(0, -d)); // Convert the deque object back to a string and return it return char_deque.join('');}let s = "neveropen";let d = 2;console.log("Left Rotation:", left_rotate_string(s, d));console.log("Right Rotation:", right_rotate_string(s, d));s = "qwertyu";d = 2;console.log("Left Rotation:", left_rotate_string(s, d));console.log("Right Rotation:", right_rotate_string(s, d)); |
Output
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), where n is the length of the input string s. This is because the deque object created from the string requires O(n) space to store all the characters. The join() function also requires O(n) space to concatenate the characters back into a string.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
