Home » Interview Questions » String Interview Questions » Rotate string to get lexicographically minimum string

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

Try It

 

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions