Lexicographically minimum string rotation in Python

In this article, we are going to learn about Lexicographically minimum string rotation in Python with some examples.

Before going to the main topic, let’s understand what is lexicographic and how lexicographically minimum string rotation works.

Lexicographically Minimum String Rotation

Lexicographical Order is the process to generalize the words according to alphabetically order.

The use of lexicographically minimum string rotation is to find the rotation of string in order to get the lowest lexicographical order of all such rotation.

For example, the lexicographically minimum string rotation of “DAABCABCA”  is “AABCABCAD”.

The string can have multiple lexicographically minimal rotations but that doesn’t matter since the rotations must be equivalent.

Some Examples:

1. Input:  PYTHON
   Outout: HONPYT

2. Input:  SPEEDY
   Outout: DYSPEE

3. Input:  PROGRAM
   Outout: AMPROGR

4. Input:  SDFTBUBSRB
   Outout: BSDFTBUBSR

5. Input:  AFADAABAAC
   Output: AABAACAFAD

Steps to solve :

1. First, add input string with itself and store it in a parameter named ‘String’.
2. Then create an array (named ‘array’ here) to store all rotations of string.
3. Take substrings of the parameter named ‘String’ to find all rotations of string and store it in an array[].
4. At last sort all those array and return array[0] which stores the minimum string rotation.

Below is the implementation :

#Function to find Lexicographically minimum string rotation.
def findMinStrRotation(String) :
    a = len(String)
    array = [0] * a
    String += String

    # Store all rotations in an array one by one.
    for i in range(a) :
        array[i] = String[i : a + i]

    array.sort()
    return array[0]

#Implement a function here
string = "EXPERT"
minLex = findMinStrRotation(string)
print(minLex)

Input:  EXPERT
Output: ERTEXP

The lexicographically minimum string rotation of ‘EXPERT’ is ‘ERTEXP’

The time complexity of the above algorithm is O(n²logn).

Booth’s Algorithm is another way to solve this problem in O(n) time.

Thank You.

Also read: Simple Student Management System Program in Python without Database