Towards a Solution to the “Runs” Conjecture

The “runs” conjecture, proposed by [Kolpakov and Kucherov, 1999], states that the number of occurrences of maximal repetitions (runs) in a string of length n is at most n. The best bound to date, due to [Crochemore and Ilie, 2007], is 1.6n. Here we improve very much this bound using a combination of theory and computer verification. Our best bound is 1.048n but actually solving the conjecture seems to be now only a matter of time.