  Given a string $s$ of length $n$ over a general alphabet and an integer $k$,
the problem is to decide whether $s$ is a concatenation of $k$ nonempty
palindromes. Two previously known solutions for this problem work in time
$O(kn)$ and $O(n\log n)$ respectively. Here we settle the complexity of this
problem in the word-RAM model, presenting an $O(n)$-time online deciding
algorithm. The algorithm simultaneously finds the minimum odd number of factors
and the minimum even number of factors in a factorization of a string into
nonempty palindromes. We also demonstrate how to get an explicit factorization
of $s$ into $k$ palindromes with an $O(n)$-time offline postprocessing.
