This is a fun puzzle. Here's my take on it. I stopped reading the article after the introduction so I could attack the problem fresh, so hopefully this isn't th

This is a fun puzzle. Here's my take on it. I stopped reading the article after the introduction so I could attack the problem fresh, so hopefully this isn't the same as what the author did. The trick is working backwards. We want to quickly count the number of occurrences of each letter in the list of number words. Knowing how to do that, we just have to do a linear scan over the cumulative counts for A, B, C, ... to find the interval into which the query index fits. If it helps prime your intuition, my inspiration is counting sort with the counts evaluated partly analytically. Number words can be divided into a fixed set of recurring components: one, two, three, four, ..., ten, eleven, twelve, thirteen, ..., twenty, thirty, ..., hundred, thousand, million, billion. Build an inverse index that maps each letter to the set of all component words that contain the letter, paired with an occurrence count. For example, the inverse index would map T to {(two, 1), (three, 1), (ten, 1), (twelve, 1), (thirteen, 2), ...}. With this in hand, the problem is reduced to counting the number of each component word in the string. Let's consider that subproblem for the component 'nine' ('nineteen' and 'ninety' are separate components) for numbers with up to n digits. Numbers with the digit pattern xxx...xxx9 each contribute one occurrence of 'nine', and there are 10^(n-1) such numbers ('... nine'). Likewise each xxx...xxx9xx contributes an occurrence, and there are again 10^(n-1) such numbers ('... nine hundred ...'), the pattern xxx...xxx9xxx has 10^(n-1) members ('... nine thousand ...'), etc. This same analysis applies to all ones components (one, two, three, ..., nine), and an analogous analysis applies to other components.