Consider the following process $\mathcal P$ on a string $S$ that is executed by Andrew the Destroyer and Werdna the Creator. Say the first character of $S$ is $c$. Case 1: If the second character of $S$ is also $c$, Andrew removes those two characters from the string $S$, and Werdna adds the characters $cc$ to the end of $R$. Then the two repeat the process on the new string. Case 2: Otherwise, say $P$ is the longest prefix substring of $S$ that contains only one $c$. Note that the character after $P$ is a $c$. Next, Andrew reverses the entirety of the substring $P'$ and puts it back in the same location (not removing any characters), and Werdna adds two copies of $P$ to the end of $R$. Then the two repeat the process on the new string. We call this one move. Clearly this process terminates since in the first case, the length of the string the process is working on decreases by $2$, and in the second case, the number of adjacent characters that are the different decreases by $1$ (since it forces two $c$'s together), hence it does not repeat. But there is no way for the process to terminate if there still exists a first character $c$, so it follows that the process terminates at the empty string. Now at the end, $R$ is a nice string, since all the strings we added to the end of it, either two $c$'s or two $P$'s, are neat. We claim that $S$ can be obtained from $R$ by a series of reductions. We will show a stronger result, that the string formed by concatenating just the strings added to $R$ in the last $k$ moves can be reduced to form the string Andrew and Werdna had when he had $k$ moves left. Proceed by induction. The base case $k=0$ is trivial. For the inductive step, it suffices to show that adding the string added to $R$ at the $k+1$th last move ``undoes'' the $k+1$th move. It's clear how in the first case, adding $cc$ is equivalent to undoing the removal of $cc$. In the second case, notice that the string before prepending two copies of $P$ begins with the reverse of $P$ since that is the result from the previous move. Thus when we prepend the two copies of $P$, a palindrome consisting of $P$ followed by its reverse is formed, which can be reduced to nothing by repeatedly deleting the two same characters in the center of the two strings. Hence we effectively replace the reverse of $P$ with $P$, which undoes the move Andrew made. Hence after adding all of the strings to $R$, we undo all of the moves Andrew made, and recover $S$, as desired. $\blacksquare$ Addendum: Here's an example of the process, with $S=ddacabbc$: \[ \stackrel{\text{Case }2}{\boxed{dd}}acabbc \implies \stackrel{\text{Case }1}{\boxed{ac}}abbc \implies \stackrel{\text{Case }1}{\boxed{caabb}}c \implies \stackrel{\text{Case }2}{\boxed{bb}}aacc \implies \stackrel{\text{Case }2}{\boxed{aa}}cc \implies \stackrel{\text{Case }2}{\boxed{cc}} \implies \text{empty} \]Hence $R = dd \mid acac \mid caabbcaabb \mid bb \mid aa \mid cc$, where the vertical lines are just for clarity. Then the following reductions turn $R$ into $S$. First, the following reduces out one palindrome by repeatedly reducing the red characters, \[ ddacaccaabb\stackrel{\text{Palindrome}}{\boxed{caab{\color{red}bb}baac}}c \implies ddacaccaabb\stackrel{\text{Palindrome}}{\boxed{caa{\color{red}bb}aac}}c \implies ddacaccaabb\stackrel{\text{Palindrome}}{\boxed{ca{\color{red}bb}ac}}c \implies \dots \implies ddacaccaabbc.\]Now similarly to the above \[ ddac\stackrel{\text{Palindrome}}{\boxed{a{\color{red}cc}a}}abbc \implies ddac\stackrel{\text{Palindrome}}{\boxed{{\color{red}aa}}}abbc \implies ddacabbc,\]as desired. $\square$