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 …