The “runs” conjecture

The “runs” conjecture, proposed by Kolpakov and Kucherov (1999) [7], states that the number of occurrences of maximal repetitions (runs) in a string of length n, , is at most n. We almost solve the conjecture by proving that . This bound is obtained using a combination of theory and computer verification.