FM-Index Rank Query

Problem

Given a Burrows-Wheeler transformed string t, a character and a prefix length i, count how many times the character appears in the first i characters of t.

This rank query is the core primitive of an FM-index. Clamp the prefix to the string length and return 0 for an empty string.

Hint

Rank is a prefix count, so only characters before index i matter.

Test cases

case 1

in: ["annb$aa","a",7]

expected: 3

case 2

in: ["annb$aa","n",3]

expected: 2

case 3

in: ["annb$aa","$",7]

expected: 1

case 4

in: ["annb$aa","z",5]

expected: 0

case 5

in: ["","a",0]

expected: 0

Starter codePython

def fm_index_rank(t, char, i):
    # Your code here
    pass

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