  We give an $\mathcal{O}(n \log n)$-time, $\mathcal{O}(n)$-space algorithm for
factoring a string into the minimum number of palindromic substrings. That is,
given a string $S [1..n]$, in $\mathcal{O}(n \log n)$ time our algorithm
returns the minimum number of palindromes $S_1,\ldots, S_\ell$ such that $S =
S_1 \cdots S_\ell$. We also show that the time complexity is $\mathcal{O}(n)$
on average and $\Omega(n\log n)$ in the worst case. The last result is based on
a characterization of the palindromic structure of Zimin words.
