Originally Posted by

**SlipEternal** The total number of size-$\displaystyle k$ substrings of string $\displaystyle S$ is $\displaystyle \max\{|S|-k+1,0\}$. So,

$\displaystyle \forall |S|\in \Bbb{Z}^+, |\{S[i,i+k-1]: 1\le i\le |S|-k+1 \text{ and }\forall j\in \Bbb{Z}^+ \text{ s.t. }1\le i\le j \le |S|-k+1, S[i,i+k-1] = S[j,j+k-1]\text{ iff }i=j\}| \le \max\{|S|-k+1,0\}$

(This is another way to write the set of all distinct size-$\displaystyle k$ substrings of the string $\displaystyle S$).

The point being, if $\displaystyle |S|-k+1$ is small in comparison to $\displaystyle |\Sigma|^k$, then $\displaystyle |S|-k+1$ is a far better upper bound.