CLR cover
Previous problem

Problem 120: Diverse Factors over a Three-Letter Alphabet

Next problem

A word $w$ is called diverse if the numbers of occurrences of its letters are pairwise different (some letters may be absent in $w$). The problem deals with diverse factors occurring in a word $x\in\{\sa{a},\sa{b},\sa{c}\}^*$.

Obviously any word of length at most 2 has no diverse factor and a word of length $3$ is not diverse if it is a permutation of the three letters. The straightforward observation follows.

Observation 1. The word $x\in\{\sa{a},\sa{b},\sa{c}\}^*$, $|x|\geq 3$, has no diverse factor if and only if its prefix of length 3 is not diverse, that is, is a permutation of the 3 letters, and is a word period of $x$.

Design a linear-time algorithm finding a longest diverse factor of a word $x$ over a three-letter alphabet.
Consider the Key property proved below.

Key property

If the word $x[0\dd n-1]\in\{\sa{a},\sa{b},\sa{c}\}^*$ has a diverse factor, it has a longest diverse factor $w=x[i\dd j]$ for which either $0\leq i \lt 3$ or $n-3\leq j \lt n$, that is, $$w \in \bigcup_{i=0}^2 \Pref(x[i\dd n-1])\cup\bigcup_{j=n-3}^{n-1} \Suff(x[0\dd j]).$$