Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \newcommand{\dif}{\mathit{diff}}% \newcommand{\asum}{\mathit{sum}}% \newcommand{\pre}{\mathit{pref}}% \newcommand{\psum}{\mathit{prev-sum}}% $

$$\dif(\sa{aaa})=0 \mbox{ and } \dif(\sa{cabbcadbeaebaabec})=4.$$ In the second word, $\sa{a}$ and $\sa{b}$ are the most frequent letters, with five occurrences and $\sa{d}$ the least frequent letter, with one occurrence.

Problem 111: Letter-Occurrence Differences

For a non-empty word $x$, $\dif(x)$ denotes the difference between the numbers of occurrences of the most frequent letter and of the least frequent letter in $x$. (they can be the same letter.)

Design an $O(n|A|)$ running time algorithm computing the value $\max\{\dif(x) \mid x \mbox{ factor of } y\}$ for a non-empty word $y$ of length $n$ over the alphabet $A$.

First consider $A=\{\sa{a},\sa{b}\}$.

125 Problems in Text Algorithms

Example

Problem 111: Letter-Occurrence Differences