How many double squares can a string contain?

Counting the types of squares rather than their occurrences, we consider the problem of bounding the number of distinct squares in a string. Fraenkel and Simpson showed in 1998 that a string of length n contains at most 2n distinct squares. Ilie presented in 2007 an asymptotic upper bound of 2n−Θ(logn). We show that a string of length n contains at most ⌊11n/6⌋ distinct squares. This new upper bound is obtained by investigating the …