Bannai et al. method proves the d-step conjecture for strings

Inspired by the d-step approach used for investigating the diameter of polytopes, Deza and Franek introduced the d-step conjecture for runs stating that the number of runs in a string of length n with exactly d distinct symbols is at most n−d. Bannai et al. showed that the number of runs in a string is at most n−3 for n≥5 by mapping each run to a set of starting positions of Lyndon roots. We show that Bannai et al. method proves that the d-step conjecture for runs holds, and stress the structural properties of run-maximal strings. In particular, we show that, up to relabelling, there is a unique run-maximal string of length 2d with d distinct symbols. The number of runs in a string of length n is shown to be at most n−4 for n≥9.