Suffix Array Doubling Rounds

Problem

Build the suffix array of s by prefix doubling: start with single-character ranks, and each round sort suffixes by the pair (rank[i], rank[i + k]) with k doubling from 1. Stop after the round where all ranks become distinct or k >= n. Return [rounds, suffix_array] where rounds counts the sorting rounds and suffix_array lists 0-based suffix starts in sorted order. For the empty string return [0, []].

Hint

Each round halves the number of distinct-rank groups; missing second halves compare as -1.

Test cases

case 1

in: ["banana"]

expected: [2,[5,3,1,0,4,2]]

case 2

in: ["aaaa"]

expected: [2,[3,2,1,0]]

case 3

in: ["abc"]

expected: [1,[0,1,2]]

case 4

in: ["abab"]

expected: [2,[2,0,3,1]]

case 5

in: [""]

expected: [0,[]]

Starter codePython

def suffix_array_rounds(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor