Problem 855

Solution:

If two identical letters are adjacent or have a single letter in between, there is clearly a palindromic substring of length (respectively) two or three. So there cannot be any such substrings.

Say we have a permutation of the word REDDER without any palindromic substrings. Let us call the first letter $X$. The second letter has to be different, let us call it $Y$. The third letter cannot be $X$ or $Y$, let it be $Z$. Again, the fourth letter cannot be $Y$ or $Z$, and we only have 3 letters to choose from, so it has to be $X$. Continuing analogously, the fifth letter has to be $Y$, and the sixth letter has to be $Z$. So any word satisfying the problem statement has to be of the form $XYZXYZ$. It is easy to check that such a word indeed does not have any palindromic substrings. $\mathrm{X}, \mathrm{Y}, \mathrm{Z}$ can be any permutation of $R$, $E$, $D$, giving a total of $6$ possibilities.