Complexity of Homogenizing a String

Question

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.

Answer 1

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.

Answer 2

Look at the number of changes from one letter to the other in your string, which you could see as a measure for the string's inhomogenity. With every (useful) move of a subsequence you reduce this number by one if the subsequence you move is preceded and followed by two distinct letters. Otherwise you reduce the inhomogenity by two.

So for a string with k changes you need at most k - l + 1 moves where l is the number of different letters in the string, because in the end l - 1 changes will remain. As a string of length n can have at most n-1 letter changes, it can need at most n - l moves. The least possible number is half of this.

The best strategy seems thus to look for subsequences of the form abbba and to move the bbb away from there. When there are none left, move whatever. You could still try to do those operations that create new abbba situations, but I think the gain will be very little. Since the worst possible strategy (without silly moves that increase the inhomogenity) uses at most twice as many moves as the optimal one, the little you might gain seems to be in no reasonable relation to the effort as the answer by isaacg with the characterization as NP-hard suggests. Unless, of course, you really only count the number of move operations and do not care about the time to decide which moves to make.

The worst case is therefore a string where every letter is different from its predecessor (and you do not get any abbba bonuses). Here you need a number of operations linear in the length of the string and almost equal to this length.

In your example, you have 5 -> 4 -> 3 changes, and 3 equals the number of letters (4) minus 1.

Side note: For an alphabet of size only two, every move that does not move a prefix or suffix of the string reduces the inhomogenity by two and thus every sequence of reasonable moves is optimal.