I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To clarify, "unique" means that the fixed-length substring or its transpose occurs at most once in $S$.
For fixed $N$ and $k$, what is the smallest possible value of $P$, and how do I construct $S$ in such a manner as to minimize $P$?
If P is odd, there are $\frac{k^P}{2}+\frac{k^\left({\frac{P+1}{2}}\right)}{2}$ distinct substrings (avoiding transpositions). If P is even, there are $\frac{k^P}{2}+\frac{k^\left({\frac{P}{2}}\right)}{2}$. $N$ must be at most this plus $P-1$. Constructing such a string shouldn't be hard, but I don't have an algorithm. Maybe this naive algorithm will work-append a character that doesn't produce a duplicate substring and within those, the one used least so far.