I will quote the problem from ACM 2003:

Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. For example, the rotations of the string “alabala” are:








and the smallest among them is “aalabal”.

As for the solution - I know I need to construct a suffix array - and let's say I can do that in O(n). My question still is, how can I find the smallest rotation in O(n)? (n=length of a string)

I'm very interested in this problem and still I somehow don't get the solution. I'm more interested in the concept and how to solve the problem and not in the concrete implementation.

Note: minimum rotation means in the same order as in an english dictionary - "dwor" is before "word" because d is before w.

EDIT: suffix array construction takes O(N)

LAST EDIT: I think I found a solution!!! What if I just merged two strings? So if the string is "alabala" the new string would me "alabalaalabala" and now I'd just construct a suffix array of this (in O(2n) = O(n)) and got the first suffix? I guess this may be right. What do you think? Thank you!

  • How do you define "minimum"? What is the metric used (maybe it is obvious but I am not an expert)?
    – Giorgio
    Jan 1, 2012 at 17:51
  • Thanks for the note! I thought the rotation had to be minimal (minimum offset), not the result of the rotation wrt lexicographical order.
    – Giorgio
    Jan 1, 2012 at 19:55
  • I am still missing something: is the construction and sorting of the suffix array included in the complexity? I imagine it takes more than O(n) to construct the array and sort it.
    – Giorgio
    Jan 1, 2012 at 23:35
  • I think the idea of repeating the original string twice is great! Then you can build the suffix array in O(2n) = O(n). But don't you need to sort it to find the minimum? This needs more than O(n), right?
    – Giorgio
    Jan 2, 2012 at 12:21
  • @Giorgio well, the suffix array itself holds the suffices already sorted. And another note, maybe slightly offtopic - don't forget that sorting can be done even in o(n) with some assumptions to the objects sorted(check out the radix sort for example)
    – Tomy
    Jan 2, 2012 at 14:38

5 Answers 5


A simple trick to construct all rotations of a string of length N is to concatenate the string with itself.

Then every N-length substring of this 2N-length string is a rotation of the original string.

Locating the "lexicographically minimal" substring is then done with your O(N) tree construction.


I'm pretty sure the information contained in a suffix array is not sufficient to help you get to O(n), but at most can help you to O(n log n). Consider this family of suffixes:


You construct the next suffix by taking the previous suffix (say aba), adding the next character not yet used and then adding the previous suffix again (so aba -> aba c aba).

Now consider these strings (the space is added for emphasis, but is not part of the string):

ad abacaba
bd abacaba
cd abacaba

For these three strings, the start of the suffix array will look like this:

(other suffixes)

Looks familiar? These strings of course is tailored to create this suffix array. Now, depending on the starting letter (a, b or c), the 'correct' index (the solution to your problem) is either the first, the second or the third suffix in the list above.

The choice of the first letter hardly affects the suffix array; in particular, it does not affect the order of the first three suffixes in the suffix array. This means that we have log n strings for which the suffix array is extremely similar but the 'correct' index is very different.

Although I have no hard proof, this strongly suggests to me that you have no choice but to compare the rotations corresponding to these first three indices in the array for their lexicographic ordering, which in turn means that you'll need at least O(n log n) time for this (as the number of alternative first characters - in our case 3 - is log n, and comparing two strings takes O(n) time).

This does not rule out the possibility of an O(n) algorithm. I merely have doubts that a suffix array helps you in achieving this running time.


The smallest rotation is the one that start with some of the suffix from the suffix array. Suffixes are lexicographically ordered. This gives you a big jumpstart:

  • you know that once you get such k that rotation starting with suffix k is smaller than rotation starting with suffix k+1, you're done (starting from the first one);
  • you can do the comparision of "rotation starting with suffix k is smaller than rotation starting with suffix k+1" in O(1) by comparing lengths of suffixes and optionally, comparing one character with one another character.

EDIT: "one character with one another character" may not always be so, it may be more than one character, but overall, you do not examine more than n characters through the whole search process, so it is O(n).

Short proof: You only examine characters when suffix k+1 is longer than suffix k, and you stop and found your solution if suffix k+1 is shorter than suffix k (then you know suffix k is the one you sought for). So you only examine characters while you are in rising (length-wise) sequence of suffixes. Since you only examine excess characters, you cannot examine more than n characters.

EDIT2: This algorithm relies on the fact the "if there are two neighbour suffixes in suffix array and the previous is shorter than the subsequent, the previous is prefix of the subsequent". If this is not true, then sorry.

EDIT3: No, it does not hold. "abaaa" has suffix table "a", "aa", "aaa", "abaaa", "baaa". But maybe this line of thought can ultimately lead to the solution, just some more details must be sophisticated more. The primary question is whether it is possible to somehow make the aforementioned comparision done by examining less characters, so it is O(n) totally, which I somehow believe may be possible. I just can't tell how, now.



Lexicographically least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations. For example, the lexicographically minimal rotation of "bbaaccaadd" would be "aaccaaddbb".


A O(n) time algorithm was proposed by Jean Pierre Duval (1983).

Given two indices i and j, Duval's algorithm compares string segments of length j - i starting at i and j (called a "duel"). If index + j - i is greater than the length of the string, the segment is formed by wrapping around.

For example, consider s = "baabbaba", i = 5 and j = 7. Since j - i = 2, the first segment starting at i = 5 is "ab". The second segment starting at j = 7 is constructed by wrapping around, and is also "ab". If the strings are lexicographically equal, like in the above example, we choose the one starting at i as the winner, which is i = 5.

The above process repeated until we have a single winner. If the input string is of odd length, the last character wins without a comparison in the first iteration.

Time complexity:

The first iteration compares n strings each of length 1 (n/2 comparisons), the second iteration may compare n/2 strings of length 2 (n/2 comparisons), and so on, until the i-th iteration compares 2 strings of length n/2 (n/2 comparisons). Since the number of winners is halved each time, the height of the recursion tree is log(n), thus giving us a O(n log(n)) algorithm. For small n, this is approximately O(n).

Space complexity is O(n) too, since in the first iteration, we have to store n/2 winners, second iteration n/4 winners, and so on. (Wikipedia claims this algorithm uses constant space, I don't understand how).

Here's a Scala implementation; feel free to convert to your favorite programming language.

def lexicographicallyMinRotation(s: String): String = {
 def duel(winners: Seq[Int]): String = {
   if (winners.size == 1) s"${s.slice(winners.head, s.length)}${s.take(winners.head)}"
   else {
     val newWinners: Seq[Int] = winners
       .sliding(2, 2)
       .map {
         case Seq(x, y) =>
           val range = y - x
           Seq(x, y)
             .map { i =>
               val segment = if (s.isDefinedAt(i + range - 1)) s.slice(i, i + range)
               else s"${s.slice(i, s.length)}${s.take(s.length - i)}"
               (i, segment)
             .reduce((a, b) => if (a._2 <= b._2) a else b)
         case xs => xs.head


I don't see anything better than O(N²).

If you have a list of N integers, you can pick the smallest in O(N) comparisons.

Here you have a list of N strings of size N (constructing them cost nothing, a string is fully determined by its starting index). You can pick the smallest in O(N) comparisons. But each comparison is O(N) basic operations. So the complexity is O(N²).

Not the answer you're looking for? Browse other questions tagged or ask your own question.