A computational framework for determining run-maximal strings

We investigate the function ρd(n)=max{r(x)|x is a (d,n)-string}, where r(x) denotes the number of runs in a string x and (d,n)-string denotes a string of length n with exactly d distinct symbols. The notion of an r-cover is presented and discussed with emphasis on the recursive computational determination of ρd(n). This notion is used as a key element of a computational framework for an efficient computation of the maximum number of runs. In particular, we were able to determine all previously known ρ2(n) values for n⩽60 in a matter of hours, confirming the results reported by Kolpakov and Kucherov, and were able to extend the computations up to and including n=74. Noticeably, these computations reveal the unexpected existence of a binary run-maximal string of length 66 containing aaaa.