Minimum Rotations Required to Get the Same String in Java

In this article, we will learn to count the total number of minimum required rotations to get the original string in Java. We can solve the problem by getting the rotations substrings of the original string or concatenating the original string to itself. 

Problem statement

We have given string str of length N. The task is to find the total number of minimum rotations we need to perform to get the original string.

Input 1

str = "bcdbcd";

Output 1

3

Explanation ? We need to make 3 rotations to get the original string.

• The string will be ?cdbcdb' after the first rotation.

• The string will be ?dbcdbc' after the second rotation.

• The string will be ?bcdbcd' after the third rotation.

Input 2

 str = ?efg'

Output 2

3

Explanation ? we need to make the total 3 left rotations to get the original string

Using Substring() method 

In this approach, we will use the substring() method to get the substrings of the particular length from the original string. After that, we concat the right and left parts of the string and count the total number of rotations using the string index.

substring(int beginIndex, int endIndex)

The substring method is used to extract a substring from the original string starting at the specified index beginIndex and ending just before the specified index endIndex.

Steps for Minimum Rotations Required to Get the same String

Following are the steps for minimum rotations required to get the same string ?

•  In the temp_str variable, store the ?alpha + alpha'.
  
•  Define the ?str_len' variable and store the length of the string.
  
• Traverse the ?temp_str' string starting from the 1st index to the string's length.
  
•  Get the substring of length equal to ?str_len' starting from the pth index.
  
• Use the equals() method to check whether alpha equals the ?substr'.
  
•  If yes, return p.
  
• At last, return ?str_len'. 

Example

Below is the Java program for minimum rotations required to get the same string using the Substring() method ?

import java.util.*;

public class Main {
    static int totalRotations(String alpha) {
        // Merge the string
        String temp_Str = alpha + alpha;
        int str_len = alpha.length();
        // traverse the string
        for (int p = 1; p <= str_len; p++) {
            // getting rotational substring
            String subStr = temp_Str.substring(p, p + alpha.length());
            // return p if str and subStr are equal
            if (alpha.equals(subStr))
                return p;
        }
        return str_len;
    }
    public static void main(String[] args) {
        String str = "bcdbcd";
        System.out.println("The total number of rotations required to get original string again are: ");
        System.out.println(totalRotations(str));
    }
}

Output

The total number of rotations required to get original string again are: 
3

Time complexity? O(N^2) as we find a substring inside the loop.

Space complexity ? O(N) to store the concatenated string.

Using Split and Merge Approach

In this approach, we will divide the original string into two parts. After that, we will merge the right and left parts of the string. If the final string is equal to the original string, we can say total rotations are equal to the index from where we divided the string into two parts.

equals(Object anObject)

The equals() method compares the original string with another string (subStr in this case) and checks if both are equal. It returns true if both strings are identical, and false otherwise.

length()

The length() method returns the length of the string, which is used to determine the number of characters in the string and to control the loop iteration.

Steps for Minimum Rotations Required to Get the same String

Following are the steps for minimum rotations required to get the same string ?

• Initialize ?operations' with zero.
  
• Traverse the string.
• Get the substring from the pth index.
  
• Get the substring from the 0th index whose length is p.
  
• If alpha and substr are the same, update the value of ?operations'.
  
• Return 0 if ?operations' equals 0. Otherwise, return the value of the ?operations' variable.

Example

Below is the Java program for minimum rotations required to get the same string using the using split and merge approach ?

import java.util.*;

public class Main {
    static int totalRotations(String alpha) {
        int operations = 0; // to store total rotations
        int len = alpha.length();
        // traverse the string
        for (int p = 1; p < alpha.length(); p++) {
            String subStr = alpha.substring(p) + alpha.substring(0, p);
            // If substring [p, len-1] + [0, p-1] == alpha, then break
            if (alpha.equals(subStr)) {
                operations = p;
                break;
            }
        }
        if (operations == 0)
            return len;
        return operations;
    }
    public static void main(String[] args) {
        String str = "bcdbc";
        System.out.println("The total number of rotations required to get the original string again are: ");
        System.out.println(totalRotations(str));
    }
}

Output

The total number of rotations required to get the original string again are: 
5

Time complexity? O(N^2) as we divide the string into two parts.

Space complexity ? O(N) to store combined substrings.

We learned two approaches to solving the problem. Also, we used the substr() method to divide the string into two parts and the ?+' operator to merge the string.