Whilst solving a question, I have come across a problem regarding the maximal number of possible distinct $k$-length binary sub-strings in an $n$-length binary string.
My thought process was that if you take some $n$-length binary string, then the number of possible sub-strings could be found as follows:
$\sum_{k=1}^{n}{n-k+1}=n^{2}-\frac{n(n+1)}{2}+n=\frac{n^{2}+n}{2}$
But this doesn't take into account the maximum possible number of distinct sub-strings, which will be $2^{k}$, when we're looking for sub-strings of length $k$.
Does anyone have any suggestions as to how I could find the maximal number of distinct sub-strings (of length $k\le n$) contained within some binary string of length $n$?
Thanks in advance!