Table of Contents
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;
}