Lexicographically Minimal String Rotation

The lexicographically minimal string rotation (or lexicographically least circular substring) is the problem of finding a string’s rotation possessing the lowest lexicographical order among all possible rotations.

For example, the lexicographically minimal rotation of bbaaccaadd is aaccaaddbb. A string can have multiple lexicographically minimal rotations, but this doesn’t matter – rotations must be equivalent.

Practice this problem

The idea is to iterate through successive rotations of the given string while keeping track of the most lexicographically minimal rotation encountered. Following is the C++, Java, and Python implementation of the idea:

C++

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

// Function to find the lexicographically minimal string rotation

string findLexicalMinRotation(string str)

{

// to store the lexicographic minimum string

string min = str;

for (int i = 0; i < str.length(); i++)

{

// left-rotate the string by 1 unit

rotate(str.begin(), str.begin() + 1, str.end());

// update the result if the rotation is minimum so far

if (str.compare(min) < 0) {

min = str;

}

return min;

}

int main()

{

string str = "bbaaccaadd";

cout << "The lexicographically minimal rotation of " << str

<< " is " << findLexicalMinRotation(str);

return 0;

}

Download Run Code

Output:

The lexicographically minimal rotation of bbaaccaadd is aaccaaddbb

Java

class Main

{

// Function to find the lexicographically minimal string rotation

public static String findLexicalMinRotation(String str)

{

// base case

if (str == null) {

return null;

}

// to store the lexicographic minimum string

String min = str;

for (int i = 0; i < str.length(); i++)

{

// left-rotate the string by 1 unit

str = str.substring(1) + str.charAt(0);

// update the result if the rotation is minimum so far

if (str.compareTo(min) < 0) {

min = str;

}

return min;

}

public static void main(String[] args)

{

String str = "bbaaccaadd";

System.out.println("The lexicographically minimal rotation of " + str

+ " is " + findLexicalMinRotation(str));

}

Download Run Code

Output:

The lexicographically minimal rotation of bbaaccaadd is aaccaaddbb

Python

# Function to find the lexicographically minimal string rotation

def findLexicalMinRotation(s):

# to store the lexicographic minimum string

min = s

for _ in range(len(s)):

# left-rotate the string by 1 unit

s = s[1:] + s[0]

# update the result if the rotation is minimum so far

if s < min:

min = s

return min

if __name__ == '__main__':

s = 'bbaaccaadd'

print("The lexicographically minimal rotation of s is",

findLexicalMinRotation(s))

Download Run Code

Output:

The lexicographically minimal rotation of bbaaccaadd is aaccaaddbb

The time complexity of the above solution is O(n²), where n is the length of the input string and doesn’t require any extra space.

Booth’s algorithm can solve this problem in O(n) time. The algorithm uses a modified preprocessing function from the Knuth–Morris–Pratt string searching algorithm. The failure function for the string is computed as normal, but the string is rotated during the computation, so some indices must be computed more than once as they wrap around. Once all indices of the failure function have been successfully computed without the string rotating again, the minimal lexicographical rotation is known to be found, and its starting index is returned.