Smallest Lexicographical Rotation

const assert = require('assert');

/**
 * Finds the number of rotations required to find the
 * smallest lexicographically ordered rotation
 * Runtime: O(N)
 * Space: 0(1)
 * @param {string} s
 */
const findMinimumRotations = (s) => {
    const concat = s + s;
    const failure = s.split('').map(c => -1);
    let rotations = 0;
    for (let i = 1; i < concat.length; i++) {
        const prefix = concat[i];
        let failureLookup = failure[i - rotations - 1];
        while (failureLookup != -1 && prefix != concat[rotations + failureLookup + 1]) {
            if (prefix < concat[rotations + failureLookup + 1]) {
                rotations = i - failureLookup - 1;
            }
            failureLookup = failure[failureLookup];
        }
        if (prefix != concat[rotations + failureLookup + 1]) {
            if (prefix < concat[rotations]) {
                rotations = i;
            }
            failure[i - rotations] = -1;
        } else {
            failure[i - rotations] = failureLookup + 1;
        }
    }
    return {
        rotations,
        word: s.substring(rotations) + s.substring(0, rotations)
    };
}

it('should find rotations', () => {
    assert.deepEqual(findMinimumRotations('bebaafc'), { rotations: 3, word: 'aafcbeb' });
    assert.deepEqual(findMinimumRotations('bcdefbcdea'), { rotations: 9, word: 'abcdefbcde' });
    assert.deepEqual(findMinimumRotations('acabaaabaa'), { rotations: 4, word: 'aaabaaacab' });
    assert.deepEqual(findMinimumRotations('cfgechge'), { rotations: 0, word: 'cfgechge' });
});