How Many Squares Must a Binary Sequence Contain?

Abstract

Let $g(n)$ be the length of a longest binary string containing at most $n$ distinct squares (two identical adjacent substrings). Then $g(0)=3$ (010 is such a string), $g(1)=7$ (0001000) and $g(2)=18$ (010011000111001101). How does the sequence $\{g(n)\}$ behave? We give a complete answer.