BWT Last Column

Problem

Compute the Burrows-Wheeler transform last column without a sentinel. Sort all n rotations of the string lexicographically and return the concatenation of their final characters. Return an empty string for empty input.

Hint

Sort the rotations, not the suffixes; for a general string they are different sets.

Test cases

case 1

in: ["banana"]

expected: "nnbaaa"

case 2

in: ["mississippi"]

expected: "pssmipissii"

case 3

in: [""]

expected: ""

case 4

in: ["a"]

expected: "a"

Starter codePython

def bwt_last_column(s):
    # Your code here
    pass

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