Lower Bounds for the Maximum Number of Runs in a String

by W. Matsubara, K. Kusano, A. Ishino, H. Bannai, A. Shinohara

Repetitions in strings is an important element in the analysis and processing of strings. It was shown in [Kolpakov and Kucherov, 1999] that when considering maximal repetitions, or runs, the maximum number of runs RUNS(n) in any string of length n is O(n), leading to a linear time algorithm for computing all the runs in a string. Although they were not able to give bounds for the constant factor, there have been several works to this end. The currently known best upper bound is RUNS(n) ≤ 1.029n, obtained by calculations based on the proof technique of [Crochemore and Ilie, 2007] and [Crochemore et al., 2008].

On the other hand, an asymptotic lower bound on RUNS(n) is presented in [Franek and Yang, 2006], where it is shown that for any ε > 0, there exists an integer N > 0 such that for any n > N, RUNS(n) ≥ (α - ε)n, where α = 3 / (1+√5) ≈ 0.927. It was conjectured in [Franek, et al., 2003] that this bound is optimal.

We proved that the conjecture was false, by showing a new lower bound α = 56733/60064 ≈ 0.944542. First we show a concrete string t of length 60064, which contains 56714 runs in it. It immediately disproves the conjecture, since 56714/60064 ≈ 0.944226 is already higher than the previous bound 0.927. Then we prove that the string tk, which is the string obtained by concatenating k copies of t, contains 56733k - 18 runs for any k ≥ 2. Since |tk| = 60064k, it yields the new lower bound 56733/60064 as k -> ∞.

You can see the details in the conference paper:

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai and Ayumi Shinohara: New Lower Bounds for the Maximum Number of Runs in a string, Prague Stringology Conference 2008.

Known lower bound

Current lower bound


[Kolpakov and Kucherov, 1999] Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: Proc. 40th Annual Symposium on Foundations of Computer Science (FOCS'99). (1999) 596-604

[Crochemore and Ilie, 2007] Crochemore, M., Ilie, L.: Maximal repetitions in strings. J. Comput. Syst. Sci. 74 (2008) 796-807

[Crochemore, et al., 2008] Crochemore, M., Ilie, L., and Tinta, L.:Towards a Solution to the ''Runs'' Conjecture. In Proc. 19th Annual Symposium on Combinatorial Pattern Matching (CPM'08). (2008) 290-302

[Franek and Yang, 2006] Franek, F., Yang, Q.: A asymptotic lower bound for the maximal-number-of-runs functions. In Proc. Prague Stringology Conference (PSC'06). (2006) 3-8

[Franek, et al., 2003] Franek, F., Simpson, R., Smyth, W.: The maximum number of runs in a string. In: Proc. 14th Australasian Workshop on Combinatorial Algorithms (AWOCA2003). (2003) 26-35