K-th smallest distinct substring

Write codeHard38 min

Your task

Given a lowercase string s, return the lexicographically smallest DISTINCT substring that is the k-th smallest among all distinct non-empty substrings (1-indexed k). If k exceeds the number of distinct substrings, return the empty string. For s='aab', the sorted distinct substrings are 'a','aa','aab','ab','b'; k=3 gives 'aab'. Length up to a few hundred.

Examples

kth_distinct_substring(s: str, k: int) -> str
Example 1
Inputkth_distinct_substring("aab", 3)
Output"aab"