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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.