Complexity of Homogenizing a String Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of integers to the other. We were able to reduce that problem to the following very natural problem that seems to have connections to edit distance, grouping by swapping, and minimum common string partition. 

Problem: We are given a string, i.e., a sequence of letters, and our goal is to  homogenize it at minimum cost. That is, we want a rearranged sequence such that all letters that are alike are next to each other. 

The only operation that is permitted is to pick up a subsequence of letters that are alike, and move that subsequence anywhere, and that costs me 1 unit.

Any help characterizing the complexity of this problem would be much appreciated!

Example:


a a b c d a b: Input
b c d a a a b: After moving the first a a to the position right after "d"
b b c d a a a: After moving the trailing b to the first position


Since the resulting string is homogeneous, we have a cost of 2. 

Note that we are not constrained in any way with respect to the output: as long as it is homogeneous, we don't need to ensure any specific order.
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.