952. The kth Word Under a Prefix

You are given n distinct words, then q queries. Each query gives a prefix p and a number k. Print the kth word in alphabetical order among the words that begin with p, or none if fewer than k of them do.

``` words apple apply apt banana band ap 1 -> apple ap 3 -> apt ap 4 -> none ban 2 -> band

words ab abc abcd abcde ab 1 -> ab ab 2 -> abc abc 1 -> abc

words cat car z 1 -> none ca 3 -> none ```

In the fourth query, the words beginning with ban are banana and band, in that order because banana and band agree on ban and then a sorts before d. So the second is band.

## Collecting first, then indexing, does too much

The direct method walks to the prefix node, gathers every word beneath it, sorts them and takes the kth. Gathering is the expensive part: a prefix matching 20000 words costs 20000 strings even when k is 1, and with 20000 queries that is 4 * 10^8 strings built and thrown away.

Problem 938 gets away with collecting because it always wants the first three and can stop after three. Here k can be anywhere, so stopping early needs a different trick.

## Counting subtrees turns the search into a descent

Give every node a counter cnt holding how many words lie at or below it, maintained during insertion exactly as in problems 947 and 948.

Walk to the prefix node. If it does not exist, or its counter is below k, the answer is none. Otherwise descend, using the counters to skip whole subtrees:

node = the node p leads to loop: if isEnd[node]: if k == 1: the answer is the path walked so far k = k - 1 for c in a .. z: if child[node][c] exists: if cnt[child] >= k: step into it, append c, break else: k = k - cnt[child]

## Why this lands on the right word

The words under a node, in alphabetical order, are: the word ending at the node itself if there is one, then all the words under child a, then all under child b, and so on. That is exactly the order the traversal of problem 944 produces, and it is a consequence of a shorter string sorting before any extension of it.

So the ordered list under a node is split into consecutive blocks whose sizes are 1 (if a word ends here) and then cnt of each child in turn. Subtracting a block's size from k when you skip it keeps k as the rank WITHIN the remaining part, and stepping into the first block big enough to contain rank k is the standard descent by counts.

Each step goes one level deeper, so the descent costs at most the length of the answer plus 26 slot checks per level, with no strings built along the way.

## The check that must come before the children

Testing isEnd before looping over the children is what puts ab before abc. Doing it afterwards returns abc for ab 1, which looks like an ordering bug and is really a block ordering bug.

## The early exit

cnt at the prefix node is how many words match the prefix at all. Comparing it with k once, before descending, is the whole "fewer than k matches" case, and it also guarantees the descent below always finds a block to enter, so the loop cannot run off the bottom of the trie.

## Cost

Building is O(total characters). Each query is O((length of p + length of the answer) * 26). Nothing here overflows: cnt is at most n, which is 20000.

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ q ≤ 20000` - Every word and every prefix is 1 to 20 lowercase English letters. - `1 ≤ k ≤ 20000` - The words are pairwise different.