O(n) algorithm to check if a string is the lexicographically smallest rotation?-CodePudding

There are a few linear time algorithms that can identify a lexicoraphically minimal rotation of a string, but they are rather complicated and involved. Does the simpler problem of checking whether a given, specific rotation is a minimal one have a simpler, more intuitive O(n) algorithm?

CodePudding user response：

Whether a string is the minimum among all its rotations can be verified in O(n):

Use a second index that runs ahead of a first index to compare characters.
When they are the same character, increase both indices.
When the second character is less than the first character, return false -- the string does not represent a minimal rotation.
When the second character is greater than the first character, reset the first index to 0.
Repeat this process until the first index has reached the end of the string, or the second index has wrapped around for a second iteration and the first index has been reset (due to the previous bullet point).
Return true when this loop ends.

This means the second index may make at most two scans over the string, giving it a O(n) complexity.

Here is a little snippet that implements the algorithm in JavaScript. It interactively outputs false/true as you enter a string input:

function isMinimalRotation(s) {
    let i = 0;
    for (let j = 1; i % s.length > 0 || j < s.length; j  ) {
        let ch = s[j % s.length];
        if (ch < s[i]) return false;
        i = ch > s[i] ? 0 : i   1;
    }
    return true;
}

// I/O Handling

const [input, span] = document.querySelectorAll("input, span");
const refresh = () => span.textContent = isMinimalRotation(input.value);
input.addEventListener("input", refresh);
refresh();

String input: <input value="1112311231124"><br>
Is minimal rotation?: <span></span>

The meaning of the for loop condition is that the loop should exit when j has iterated all elements at least once, and i has been reset to 0, or has also iterated all elements (i == s.length). As one of these two i values is guaranteed to occur during j's second iteration of the array, the loop is guaranteed to end before j makes a third iteration.

In Python you could code it like this:

def is_minimal_rotation(s):
    i = 0
    n = len(s)
    for j in range(1, n*2):
        ch = s[j % n]
        if ch < s[i]:
            return False
        i = 0 if ch > s[i] else i   1
        if i in (0, n) and j >= n:
            return True