2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ So it's $O(|\Sigma|^2)$ nice! $\endgroup$ – BananaCats Author Aug 3 '19 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.