Complexity of Homogenizing a String
This problem is NP-complete, by reduction from Minimum Hitting Set.

In minimum hitting set, we are given a universe, $U$, and a set of sets $S$ such that $\forall s \in S, s \subset U$. The objective is to find $H \subset U$ of smallest size such that $\forall s \in S, \exists h \in H$ such that $h \in s$.

The reduction is as follows:


The string is as follows: For each element $u \in U$, there will be a two characters of the string, $u'$. Between these characters will a character $s'$ for each $s \in S$ such that $u \in s$. Between the pairs of $u'$s, there will be unique characters that are not repeated in the string.
To homogenize the string, the $s'$ character must be moved $|s|-1$ times, for each $s$.  Additionally, for each $u$, the $u'$ character must be moved once, unless every $s'$ between the pair of $u'$ has been moved elsewhere.
Therefore, to minimize the number of moves necessary to homogenize the string, we wish to maximize the number of $u'$ such that every $s'$ has been moved elsewhere. The $u'$s where the $s'$s have not been moved elsewhere must together contain a $s'$ for every $s \in S$, so they must for a hitting set. Moreover, any such hitting set may serve as the ending locations of the $s'$s, by moving each $s$ to the $u$ which hits it.
Thus, the number of moves to homogenize this string is equal to $\sum |s| + |H^*|$, where $H^*$ is the minimum hitting set.


Since minimum hitting set is NP-Hard, optimally homogenizing a string is as well. Since the moves form a witness, it is NP-Complete.