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!
- 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.