Singing Game

Let’s say we have a string s = “abbacdc” and we have stored all the positions(1-based indexing) where each of the characters has occurred, for example ‘a’ has occurred at positions $1$ and $4$, ‘b’ has occurred at positions $2$ and $3$ and so on.

Now if for some query $l = 4$ and $r = 7$ then the first occurrence of ‘a’, ‘c’ and ‘d’ are at position $4$, $5$ and $6$ respectively. So $k$ for ‘a’ will be $1$, ‘c’ will be $2$ and ‘d’ will be $3$. For each character from ‘a’ to ‘z’, it can be easily found these positions by doing Binary Search on the stored positions of the characters. As we have got $k$ for the characters of the substring, now we can easily calculate the length of the substring using the count of the characters in the substring. Final complexity will be $O(n*26*logn)$.