As we know the number of different substrings has the upper bound $O(n^{2})$.


Consider the strings on $\{0,1\}$ alphabet. Can I build a string with $\Omega(n^{2})$ different substrings?


Actually I was thinking about the Thue-Morse sequence. We could use the fact that there are no two $s\_1,s\_2\in$ the Thue-Morse sequence, such that $s\_1\cap s\_2>0$.



Building the string on $\{0,1\}$ alphabet with $\Omega(n^{2})$ different substrings
Consider the $2n$-bit string $0^n1^n$. There is an injective map $\{1,\dotsc,n\}^2 \ni (i,j) \mapsto 0^i1^j \in \text{Sub}(0^n1^n)$, which shows that there are at least $n^2$ different substrings.


