C++ Program for Left Rotation and Right Rotation of a String

0 0 4 minutes read

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 = "zambiatek"
        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 d
void 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 d
void rightrotate(string &s, int d)
{
   leftrotate(s, s.length()-d);
}
 
// Driver code
int main()
{
    string str1 = "zambiatek";
    leftrotate(str1, 2);
    cout << str1 << endl;
 
    string str2 = "zambiatek";
    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 string
string 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 string
string rightrotate(string str1, int n)
{
 
    return leftrotate(str1, str1.size() - n);
}
 
// Driver code
int main()
{
    string str1 = leftrotate("zambiatek", 2);
    cout << str1 << endl;
 
    string str2 = rightrotate("zambiatek", 2);
    cout << str2 << endl;
    return 0;
}
 
// This code is contributed by Susobhan Akhuli

Output

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 function
string 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 function
string 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 = "zambiatek";
    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

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)

Please refer complete article on Left Rotation and Right Rotation of a String for more details!

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 zambiatek!