CareerCup

Here is a O(n) solution :
We concat the string twice, then browse the string from left to right,
keeping the the start position of the current answer seen so far.
When we see a letter that would possibly be the start pos of a new answer, we do
not update it yet, instead we keep an offset that defines the size of the prefix
that has been checked for comparison of the current best answer and the possible
new answer.

std::string lex_min(std::string& str)
{
int size = str.size();
std::string input = str + str;

int offset = 0;
int answer = -1;

for (int i = 0; i < size * 2; i++)
{
if (answer == -1)
{
// First character
answer = i;
}
else if (input[i] < input[answer])
{
// We definitely have a new answer here
answer = i;
// Reset the offset for future tie
offset = 0;
}
else if (input[i] == input[answer + offset])
{
// We might have another answer here
// move the offset forward
offset++;
}
else if (input[i] < input[answer + offset])
{
// we have found something even better
// than what we had before
// Set marker for new answer
answer = i - offset;
offset = 0;
}
else
{
offset = 0;
}
}

return input.substr(answer, size);
}

Given string S.

For String S' = SS (append S to itself).

Compute suffix tree (ST) of S.

Now do a depth first search of ST, picking the children in lexicographic order.

Pick the first node you find, at depth |S|.

Linear time algorithm.

appending the string with itself(since circular) and finding substrings(from position i to i+l)
(i.e) HELLO -> HELLOHELLO

min=s; l=s.size();
s+=s;
for(i=0;i<l;i++)
 {str=s.substr(i,i+l);if(str<min)min=str;}

Easy to find one Omega(nlogn) solution. n = |s|
(1) s = s + s, for example, s="abc", then s = "abc"+"abc"="abcabc"
(2) for any integer i, t[i]=s[i,i+1...i+n-1]
(3) we want to find such i that t[i] is lexicographic mininum.

now we can not store all t[i] (the space may be O(n^2))
so we want to write one function cmp(i,j)
to compare t[i] and t[j], but how?

First of all, we calculate the Hash array. O(2n)=O(n)
Hash[i]=s[0]*p^(i)+s[1]*p^(i-1)+...+s[i-1]*p^1+s[i]

If we want to get the Hash value of the substring s[x..y], we can simply have:
Hash(x..y) = Hash[y]-Hash[x-1]*pow(p,y-x+1) O(1) // we can calculate pow(p,*) at first in O(2n)=O(n) time

Then for 2 given integer i and j, we wanna compare t[i] and t[j]
(1) we find LCP(t[i],t[j]). Binary search with Hash O(logn)
(2) compare the (LCP(t[i],t[j])+1) -th value;

for example:
t[i]="abcd"
t[j]="abef"
LCP(t[i],t[j])=2
so we compare t[i][3] = 'c' and t[j][3] = 'e'
then we get the result.

Now we can compare t[i], t[j] in O(logn) time

Then we use one random algorithm to find the k-th "i". O(n * logn) (The algorithm is something like the quick-sort)

Algorithm

maintain the starting index of the minimum string and the ending index from the start, which contains duplicate characters with the substring ending at the current index

if the character at the current index is equal to the character at the ending index, increment the ending index
if the character at the current index is smaller than the character at the ending index, set the ending index to zero
if the character at the current index is bigger than the character at the ending index, set the start to the index where the duplicate substring ending at the current index starts

Time: O(n)

public String minString(String a)
        {
                int n = a.length();
                int start = 0; // the starting index of the minimum string
                int i = 0; // the ending index from start, which contains duplicate characters 
                for(int k = 1; k < n || i % n > 0 ; k++) {
                        if(a.charAt((start + i) % n) == a.charAt((start + k) % n)) {
                                i++;
                        } else if(a.charAt((start + i) % n) < a.charAt((start + k) % n)) {
                                i = 0;
                        } else {
                                start = (start + k - i) % n;
                                k = (k - i - 1) % n;
                                i = 0;
                        }
                }
                return a.substring(start) + a.substring(0, start);
        }

public String minArr(String s)
{
   char min = 'Z';
   for(int i = 0; i < s.length(); i++)
      if(s.charAt(i) < min)
         min = s.charAt(i);
   ArrayList<Integer> pos = new ArrayList<Integer>();
   for(int i = 0; i < s.length(); i++)
      if(s.charAt(i) == min)
         pos.add(i);
   int p = getMinPos(pos, s);
   return s.substring(p) + s.substring(0, p);
}

public int getMinPos(ArrayList<Integer> pos, String s)
{
   int add = 1;
   int len = s.length();
   s += s;
   while(pos.size() > 1 && add < len)
   {
      for(int i = 1; i < pos.size(); )
      {
          if(s.charAt(pos.get(i)+add) < s.charAt(pos.get(i-1)+add))
             pos.remove(i-1);
          else if(s.charAt(pos.get(i)+add) > s.charAt(pos.get(i-1)+add))
             pos.remove(i);
          else
             i++;
      }
      add++;
   }
   return pos.get(0);
}

1) Use a trie and insert in it all the N length strings like BCABDADAB,CABDADABB etc. Find the left most path in this trie.
O(N*N) , O(N*N)
2) Find out all the rounded strings of length N (the strings used in 1)) that start with the smallest char i.e ABDADABBC,ADABBCABD,ABBCABDAD (all start with A, ans would be one of these) Find lexicographical min in O(N).
3) Or instead of copying into temp strings (3 O(N) strings)) use 3 pointers with start address of 3 A's. Max O(N) space for index pointers.
for(l=0;l<N;l++)
{
for(k=0;k<ptListLen,k++) //len =3
find the min of Str[(ptList[k]+l)%N] (when l=1, you will be comparing B,D,B 1st index in the three strings.
if(multiple equal mins (like B) discard other pointer indices other that min and continue searching till you get only only 1 min.
}
T : O(N*N), S=O(N) : time can be reduced is getting the count of mins can be reduced somehow

since we're comparing strings with the same length, assuming there are N letters in the alphabet, you'd suffice to transform the string and it's rotated versions to an integer by changing from base N to for example base 10 and keep a record of the smallest.
This can be done on O(n) time and O(1) space.

#include<iostream>
#include<string>
using namespace std;
int main(){
string in;
cin>>in;
int l = in.length();

string dbl = in+in;
int lt=2*l;
string min = in;
string tmp=in;
for(int i=0;i<l;i++){
tmp=dbl.substr(i,l);
if(tmp<min)
min=tmp;
}
cout<<min<<"\n";

return 0;
}

Brute force would be O(n*n). That is comparing all possible permutation.
We can do little better if we calculate permutation only starting with minimum element i.e. A. In this example we have 3 permutations for that.

Treat the string as a number in base 27.

for (i = string.length-1; i >= 0; i--)
    number = string[i] + number * 27;

min_location = string.length - 1;
min_number = number;
for (i = string.length-1; i >= 0; i--) {
    new_number = (number - (string[i] * pow (27 , 4))) * 27 + string[i];
    if (new_number < min_number) {
           min_location = i;
           min_number = new_number;
     }
}

I take my words back

I am no more Curious

Another "brute-force" approach, but hopefully less brute-force than others. Time complexity is still O(n^2).

int minStart(char[] arr) {
  int len = arr.length;
  char[] repeat = new char[2*len];
  System.arraycopy(arr, 0, repeat, 0, len);
  System.arraycopy(arr, 0, repeat, len, len);
  
  int minStart = 0;
  for(int i=1; i<len; i++) {
    for(int j=0; j<len; j++) {
      if(repeat[minStart+j] < repeat[i+j])
        break;
      if(repeat[minStart+j] > repeat[i+j]) {
        minStart = i;
        break;
      }
    }
  }

  return minStart;
}