# What is the max length string that can be formed using k distinct characters so that all of its substrings are unique.

Given k distinct characters , what is the max length string that can be formed using these characters one or more time so that all the sub-string whose size is greater than one are unique.

Eg - For k = 3 {a,b,c}

A string of max 10 length can be made so that all of its substring whose length is greater than one are unique.(45 sub strings)

String = aabbccacba . Its sub-string of size greater than 2 are

{aa , aab , aabb , aabbc , aabbcc , aabbcca , aabbccac , aabbccacb , aabbccacba , ab , abb , abbc , abbcc , abbcca , abbccac , abbccacb , abbccacba , bb , bbc , bbcc , bbcca , bbccac , bbccacb , bbccacba , bc , bcc , bcca , bccac , bccacb , bccacba , cc , cca , ccac , ccacb , ccacba , ca , cac , cacb , cacba , ac , acb , acba , cb , cba , ba} all of which are unique.

The answer is $$k^2 + 1$$. It suffices to take a De Bruijn sequence on a $$k$$-letter alphabet and to add the first letter of the sequence at the end of the word (since De Bruijn sequences are usually defined as cyclic sequences).
The resulting word $$u_k$$ has length $$k^2 + 1$$ and contains exactly once every word of length $$2$$ as a factor. Suppose that a word $$w$$ of length $$> 2$$ occurs at least twice as a factor of $$u_k$$. If $$p$$ is the prefix of length $$2$$ of $$w$$, then $$p$$ would occur at least twice as a factor of $$u_k$$, which is not possible. Thus every factor of $$u_k$$ occurs exactly once in $$u_k$$.