I have 2 questions in mind, just out of curiousity :). They both consider [tries](https://en.wikipedia.org/wiki/Trie) (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 \leq 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.
↵
1) For some 2 natural numbers $N$ and $K$ (suppose $K \leq 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.
