# Rotate string to get lexicographically minimum string

## Write a function to find lexicographically minimum string in a circular string(array).

### Example

a) Input string : CDAABD
Output : AABDCD

b) Input string : CDAB
Output : ABCD

Time complexity : O(n2logn)

## Algorithm

1. Create an array of strings to store all rotations.

2. Create a concatenation of string with itself.

3. Store all rotations of the input string in the array by getting substrings of length n from the concatenated string.

4. Sort the all rotations in lexicographic order.

5. Return array[0], which is minimum string rotation lexicographically.

### Algorithm working

Input string : CDAABD

Apply algorithm,

concatenated_string = CDAABDCDAABD
n = 6 (length of string)

a) For i =0,
array[i] = concatenated_string.substr(i, n)
array[0] =CDAABD

b) For i =1,
array[i] = concatenated_string.substr(i, n)
array[1] = DAABDC

c) For i =2,
array[i] = concatenated_string.substr(i, n)
array[2] = AABDCD

d) For i =3,
array[i] = concatenated_string.substr(i, n)
array[3] = ABDCDA

e) For i =4,
array[i] = concatenated_string.substr(i, n)
array[4] = BDCDAA

f) For i =5,
array[i] = concatenated_string.substr(i, n)
array[5] = DCDAAB

Therefore,

array[] = [“CDAABD”,“DAABDC”,“AABDCD”,“ABDCDA”,BDCDAA”,“DCDAAB” ]
Sort this array lexicographically,
array[] = [“AABDCD”,“ ABDCDA”,“BDCDAA”,“CDAABD”,“DAABDC”,“DCDAAB” ]
return array[0], Therefore, Final output: AABDCD

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

string MinString(string str)
{
int length = str.length();//length of string
string array[length];//array to store all string rotations
//concatination to string to itself
string concatenated_string = str + str;
//store all string rotations from the concatenated string
//one by one (substrings)
for (int i = 0; i < length; i++)
{
array[i] = concatenated_string.substr(i, length);
}
//sort the array
sort(array, array+length);
//return minimum string
return array[0];
}

//Main function
int main()
{
cout<<MinString("CDAABD")<<endl;
cout<<MinString("CDAB")<<endl;

}``````

Scroll to Top