Java Program for Left Rotation and Right Rotation of a String



Rotation means we have to shift each character either in a forward direction or backward direction. Forward direction means right rotation (Or anticlockwise) and backward direction means left rotation (Or clockwise).

In this problem, we have given a string of characters of size n and integer d. Here d is less than n. 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.

Input 1

str = “apple”, d = 2

Output 1

Left Rotation = “pleap”
Right Rotation = “leapp”

Approaches

We have seen the example above for the given string and integer, let us move to the approaches:

Approach 1: Substring Method

The idea of this approach is that. Rotated the string using the reverse method.

For the left rotation: First, added the last n-d character of the string then added the first d character of the string.

For the right rotation: Need to pass the string and size of the string minus d to the forLeftRotation function to get the right rotation string.

Example

import java.util.*;
import java.io.*;
public class Rotation{
    // In-place rotation of string str by d to the left.
    static String forLeftRotation(String str, int d)  {
       String first = str.substring(d);
       String second = str.substring(0, d);
       String res = first + second ;
       return res;
    } 
    // In-place rotation of string 'str' by d to the right.
    static String forRightRotation(String str, int d) {
       int n = str.length();
       int newD = n-d;
       return forLeftRotation(str, newD);
    } 
    public static void main(String args[]) {
       String str = "apple"; //given string
       int d = 2; //given integer         
       String strL = str; // store given string for left rotation
       //Call the function to rotate the string toward the left
       strL = forLeftRotation(strL, d);
       System.out.println("Left Rotation: "+strL);        
       String strR = str; // store given string for right rotation
       //Call the function to rotate the string toward the right
       strR = forRightRotation(strR, d);
       System.out.println("Right Rotation: "+strR);            
   }
}

Output

Left Rotation: pleap
Right Rotation: leapp

Approach 2: Using Extended String

The concept is that we can use an extended string, which is twice as long as a conventional string, to rotate a string. Uses the extended string for left rotation from index d to index len(string) + d. And for the right rotation, pass the string to the forLeftRotation function to rotate the string left by the size of the string minus d.

Example

import java.io.*;
import java.util.*;  
public class Rotation{  
   // rotation of string str by d to the left
   static String forLeftRotation(String str, int d)  {
      String temp = str + str; // Extended string
      int idx = str.length(); // Constructing a new rotated string's index   
      String leftFirst = temp.substring(d, d + idx);    
      return leftFirst; // return left rotated string
   } 
   // Rotating the string str using extended string by d
   static String forRightRotation(String str, int d) {
      return forLeftRotation(str, str.length() - d);
   }
   public static void main(String args[])  {
      String str = "apple"; 
      int d = 2;         
      String strL = forLeftRotation(str, d);
      System.out.println("Left Rotation: "+strL);       
      String strR = forRightRotation(str, d);
      System.out.println("Right Rotation: "+strR);
   }
}

Output

Left Rotation: pleap
Right Rotation: leapp

Approach 3: Using dequeue

This method defines two deque-based methods for rotating a string to the left and the right. The functions forLeftRotation() and forRightRotation() both rotate the string str by d places to the left and to the right, respectively. The rotated string is returned by both functions.

Example

import java.io.*;
import java.util.*;  
public class Rotation{
   // create function to rotated string towards left
   static String forLeftRotation(String str, int d)   {
      // Create Deque to store characters of the string
      Deque<Character> dq
      = new ArrayDeque<Character>();
      for (char ch : str.toCharArray()) {
         dq.add(ch);
      }
      // first d character of the string is rotated left using deque
      for (int i = 0; i < d; i++) {
         dq.addLast(dq.removeFirst());
      } 
      // convert deque to string
      StringBuilder leftStr = new StringBuilder();
      for (char ch : dq) {
         leftStr.append(ch);
      }
      return leftStr.toString();
   }
   // create function to rotated string towards right
   static String forRightRotation(String str, int d) {
      // Create Deque to store characters of the string
      Deque<Character> dq
      = new ArrayDeque<Character>();
      for (char ch : str.toCharArray()) {
          dq.add(ch);
      } 
      // first d character of the string is rotated right using deque
      for (int i = 0; i < d; i++) {
         dq.addFirst(dq.removeLast());
      } 
      // convert deque to string
      StringBuilder rightStr = new StringBuilder();
      for (char ch : dq) {
         rightStr.append(ch);
      }
      return rightStr.toString();
   }  
   public static void main(String args[]) {
      String str = "apple"; 
      int d = 2;          
      String strL = forLeftRotation(str, d);
      System.out.println("Left Rotation: "+strL);        
      String strR = forRightRotation(str, d);
      System.out.println("Right Rotation: "+strR);
   }
}

Output

Left Rotation: pleap
Right Rotation: leapp

Note for all the above 3 methods

In all the above 3 methods, 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.length())

Conclusion

Here discussed the Java program for left and right rotation of the string. There are three methods are implemented to solve this problem. They are the substring method, extended string method, and deque method with a time complexity of O(N) for all of them.


Advertisements