题目内容
小红拿到一个长度为 n 的字符串 s，对于 s ，共有 n 个前缀字符串，例如：s="adcb" ，那么 s 的前缀字符串依次为 {"a","ad","adc","adcb"}，现在小红会对这 n 个字符串先在其内部按照字母表顺序从小到大的排序规则先排好，为 {"a","ad","acd","abcd"} 。然后再对 n 个字符串按照字典序从小到大的排序规则排好，为 {“a",“abcd",“acd","ad"}
小红想知道最后排好集合中第 k 小的字符串。
从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的字母表顺序得出字符串的大小，称为字典序比较。如果比较到其中一个字符串的结尾时依旧相同，则较短的字符串较小。
题目大意
给定一个长度为 n 的小写字母串 s，考虑它的所有前缀 s[1..1], s[1..2], …, s[1..n]。
先把每个前缀内部的字符按字母表顺序排序（例如 “adcb” → “abcd”），得到 t₁, t₂, …, tₙ。
再对这 n 个字符串按字典序排序，求第 k 小的结果。
字典序比较时，从头比到尾，首个不同字符字母小者在前；如果一个串是另一个的前缀，则短串在前。
思路
- 前缀字符计数
- 用 cnt[i][d] 表示前缀 s[1..i] 中字母（‘a’+d）出现的次数。
- cnt[0][*]=0；
