# How long can a string be before it must have considerable repeated substrings?

A considerable repeated substring $$t \leqslant s \in \Sigma^*$$ is a string of length $$2$$ that occurs at least 3 times disjointly within $$s$$ or a string of length $$3$$ or more that occurs at least $$2$$ times disjointly within $$s$$.

So for $$|\Sigma| = 1$$, $$s = a^n$$ it's $$|s| = 6$$, since we have $$(aa)(aa)(aa)$$ or $$(aaa)(aaa)$$ but not less than 6, since you can't do the same for $$n = 5, 4, 3, 2, 1$$.

Thus it's going to be a function of alphabet size.

For $$|\Sigma| = 2$$. I'll work out the possibilities:

$$aaaaabbbbbaba$$

So it's $$|s| = 13$$. Not too shabby. My strategy was to make the string as long as possible before switching chars.

What's the general estimate?

One more example: $$|\Sigma| = 3$$ $$s = aaaaabbbbbcccccacbacabcba$$ which is probably not quite exact, since I'm not sure how I'm actually deciding, but $$f(3) = |s| = 25$$.

I'm fairly sure that $$f(n) = 2n^2 + 2n + 1$$, where $$f(n)$$ is the maximal length of a string in a language of $$n$$ symbols that does not have considerable repeated substrings. Here's why:
Let $$|\Sigma| = n$$. In a string of length $$n^2 + 1$$, there are $$n^2$$ two-character substrings. If this has minimal repetition of two-character strings, then that means every two-character string is visited -- except that you've said that interlocking repetitions don't count, so in the case of the strings $$aa$$, $$bb$$, $$cc$$ and so on the substring that begins at the second character might be the same without counting as a new repetition (e.g., "$$aaa$$" has two "$$aa$$" substrings, but they only count as one disjoint instance). There are $$n$$ of those. So the maximum-length string with no repetitions of a two-character substring has length $$n^2 + n + 1$$ (the $$+1$$ at the end is just to give the last two-character substring its second character).
Then we can get another $$n^2 + n$$ by repeating the sequence, burning up our second repetition of each two-character substring; the $$+1$$ at the end of the previous string gets subsumed, but we get a new $$+1$$ at the end of this one. Now we have a string of length $$2n^2 + 2n + 1$$, but every two-character substring has two disjoint instances, so we can't extend it any further. Note that this matches the examples you gave.
Notice that I haven't dealt with the three-character sequences; that might restrict the length further when $$n$$ is larger, but it doesn't seem to have had any effect for low $$n$$.
• So it's $O(|\Sigma|^2)$ nice! – BananaCats Author Aug 3 '19 at 5:22