Lexicographically Smallest Rotation

Problem Overview

Checking every rotation against every other takes quadratic time.

Intuition

Checking every rotation against every other takes quadratic time. Instead, keep two candidate starting positions and compare the rotations that begin there one character at a time. When they first differ after k equal characters, the candidate with the larger character loses, and so does every start up to k positions after it, because each of those rotations would lose the same comparison. Every comparison either extends a match or discards at least one start, so the whole search is linear.

Algorithm

1Copy the string into a character array and set i = 0, j = 1, k = 0.
2While i, j, and k are all below n, compare the characters at i + k and j + k, wrapping past the end by subtracting n.
3If they are equal, increase k.
4If the character at i is larger, move i forward by k + 1. Otherwise move j forward by k + 1. If the two starts collide, move j one more step. Reset k to 0.
5The smaller of i and j is the start of the smallest rotation. Copy the suffix from there, then the prefix before it.

Example Walkthrough

Input: s = "bca"

1. Start 0 reads b and start 1 reads c. b is smaller, so j moves to 2.
2. Start 0 reads b and start 2 reads a. a is smaller, so i moves to 1.
3. Start 1 reads c and start 2 reads a. i moves to 2, collides with j, and j moves to 3, which ends the loop.

Output: "abc"

Common Pitfalls

• After a mismatch, skip k + 1 positions, not just one. That jump is what keeps the algorithm linear.
• If both pointers land on the same start, separate them, or every later comparison matches itself.
• A string of repeated characters lets k reach n. The loop must stop there and still return the rotation at start 0.
• Wrap indices with one subtraction. Each index is below 2n, so a modulo on every step is unnecessary.

Lexicographically Smallest Rotation.java

Java

// Approach: Two candidate starts i and j race over the doubled string. When
// they first differ after k equal characters, every start from the larger
// candidate through k positions later cannot be the minimum, so that
// candidate jumps past them. The surviving start is the smallest rotation.
// Indices wrap with a subtraction instead of a modulo, and the answer is
// copied into one array.
// Complexity: O(n) time, O(n) extra space for the char array and result.
class Solution {
    public String lexiString(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int i = 0;
        int j = 1;
        int k = 0;

        while (i < n && j < n && k < n) {
            int a = i + k;
            int b = j + k;
            if (a >= n)
                a -= n;
            if (b >= n)
                b -= n;

            if (c[a] == c[b]) {
                k++;
                continue;
            }
            if (c[a] > c[b])
                i += k + 1;
            else
                j += k + 1;
            if (i == j)
                j++;
            k = 0;
        }

        int start = Math.min(i, j);
        char[] out = new char[n];
        System.arraycopy(c, start, out, 0, n - start);
        System.arraycopy(c, 0, out, n - start, start);
        return new String(out);
    }
}

Was this solution helpful?