alphabet partitioning scheme. Let $t$ be the string in which each character $s [i]$ is replaced by the number $$t[i] = \lceil \lg (n / {\ensuremath{\mathsf{occ}\left( {s [i]}, {s} \right)}}) \lg n \rceil
\leq \left\lceil \lg^2 n \right\rceil\,.$$ For $0 \leq \ell \leq \lceil \lg^2 n\rceil$, let $s_\ell$ be the string consisting of those characters $s [i]$ that were replaced by $\ell$ in $t$, and let $\sigma_\ell$ be the number of distinct characters in $s_\ell$. More precisely, $s_\ell$ will be a sequence over alphabet $[1..\sigma_\ell]$. The mapping with $[1..\sigma]$ will be done by storing another sequence ${\ensuremath{{m}}}[1..\sigma]$ so that ${\ensuremath{{m}}}[a]$ will be the sub-alphabet number assigned to character $a$. Hence character $a$ is mapped to character ${\ensuremath{{m}}}.{\ensuremath{\mathsf{rank}}}_{{\ensuremath{{m}}}[a]}(a)$ in string $s_{{\ensuremath{{m}}}[a]}$, and symbol $x \in [1..\sigma_\ell]$ in $s_\ell$ corresponds to character ${\ensuremath{{m}}}.{\ensuremath{\mathsf{select}}}_\ell(x)$.

Notice that, if both $a$ and $b$ are replaced by the same number in $t$, then $\lg (n / {\ensuremath{\mathsf{occ}\left( {b}, {s} \right)}}) - \lg (n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) < 1 / \lg n$ and so ${\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} / {\ensuremath{\mathsf{occ}\left( {b}, {s} \right)}} < 2^{1 / \lg n}$. It follows that, if $a$ is replaced by $\ell$ in $t$, then $\sigma_\ell < 2^{1 / \lg 