Rotate string to get lexicographically minimum string


StringViews 2640

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;
       
}

Try It

 

Translate »