Burrows-Wheeler Transform

Problem

Compute the Burrows-Wheeler transform of a string: append a sentinel dollar sign, sort all rotations of the result, and take the last column of the sorted rotations.

For example banana becomes annb dollar sign aa. Assume the input contains no dollar sign; the empty string transforms to a single sentinel.

Hint

The sentinel makes the rotation order unambiguous and all rotations distinct.

Test cases

case 1

in: ["banana"]

expected: "annb$aa"

case 2

in: [""]

expected: "$"

case 3

in: ["a"]

expected: "a$"

case 4

in: ["ab"]

expected: "b$a"

case 5

in: ["mississippi"]

expected: "ipssm$pissii"

Starter codePython

def burrows_wheeler_transform(s):
    # Your code here
    pass

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