Explanation

• The Burrows-Wheeler Transform (BWT) is a string transformation algorithm used in data compression. It reorders the characters of a string into runs of similar characters, making it easier to compress.

Steps

• Generate all cyclic rotations of the string.
• Sort these rotations lexicographically.
• The last column of the sorted rotations is the BWT of the string.

Time Complexity

• Time complexity: O(n log n) for sorting the rotations.

def burrows_wheeler_transform(s):
    s = s + '$'  # Adding a sentinel character
    rotations = [s[i:] + s[:i] for i in range(len(s))]
    rotations.sort()
    return ''.join([rotation[-1] for rotation in rotations])
 
# Example usage
s = "banana"
bwt = burrows_wheeler_transform(s)
print(f"BWT of '{s}' is '{bwt}'")