I have 2 questions in mind, just out of curiousity :). They both consider tries (not compressed). Also note — by a trie's size I'm not considering its root (even though, it does not matter for the purpose of this problem).

1) For some 2 natural numbers *N* and *K* (suppose *K* ≤ *N*), what is the maximal size of a trie that can be achieved if you take some string *S* of length *N*, with the size of its language (number of distinct characters it can contain) being *K*, and insert into the trie all its suffixes (so, a suffix trie)?

For instance, if *N* = 2, *K* = 2, we can form the string "ab", which makes the trie of size 3. On the other hand, if *N* = 10, *K* = 1, the only string we can form is "aaaaaaaaaa" which makes the trie size 10.

2) How do you form such a string with maximal trie size? An algorithm or an idea, both are acceptable.

Thanks.