The Number of Runs in Nonbinary Strings

Description

A run is a string of the form α^k for α∈Σ^* and k≥2. For example, the string bananatree contains the runs anana = (an) ^5/2 and ee = e². It is known that the number of runs in a string of length n is at most n-1 [H. Bannai et al.: The "Runs" Theorem. SIAM J. Comput. 46(5): 1501-1514 (2017)]. However, for binary strings a stronger upper bound 183/193 is known [S. Holub: Prefix frequency of lost positions. Theor. Comput. Sci. 684: 43-52 (2017)]. The purpose of this project is to extend this stronger upper bound to nonbinary strings. Maybe in a first step, one could try to extend the techniques to ternary strings and then generalize what happens for larger alphabets.