Lexicographically minimal string rotation or lexicographically least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations.

For example, the lexicographically minimal rotation of `bbaaccaadd`

would be `aaccaaddbb`

. It is possible for a string to have multiple lexicographically minimal rotations, but this does not matter as the rotations must be equivalent.

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

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <string> #include <algorithm> using namespace std; // Function to find Lexicographically minimal string rotation string findLexicalMinRotation(string str) { // To store lexicographic minimum string string min = str; for (int i = 0; i < str.length(); i++) { // left rotate string by 1 unit rotate(str.begin(), str.begin() + 1, str.end()); // check if the rotation is minimum so far if (str.compare(min) < 0) min = str; } return min; } // main function int main() { string str = "bbaaccaadd"; cout << "The lexicographically minimal rotation of " << str << " is " << findLexicalMinRotation(str); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class LexicalMinRotation { // Function to find Lexicographically minimal string rotation public static String findLexicalMinRotation(String str) { // To store lexicographic minimum string String min = str; for (int i = 0; i < str.length(); i++) { // left rotate string by 1 unit str = str.substring(1) + str.charAt(0); // check if the rotation is minimum so far if (str.compareTo(min) < 0) { min = str; } } return min; } // main function public static void main(String[] args) { String str = "bbaaccaadd"; System.out.println("The lexicographically minimal rotation of " + str + " is " + findLexicalMinRotation(str)); } } |

`Output:`

The lexicographically minimal rotation of bbaaccaadd is aaccaaddbb

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(1).

Booth’s Algorithm can solve this problem in O(n^{}) time. The algorithm uses a modified preprocessing function from the Knuth-Morris-Pratt string search 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. We will be soon discussing implementation of Booth’s Algorithm.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply