Minimum Common String Partition Problem: Hardness and Approximations: APX-hardness with at most two copies per letterResearch Paper
Two strings can contain exactly the same letters and still arrange them very differently. A useful measure of that difference asks how many contiguous pieces are needed so that the pieces of one string can be rearranged into the other. This minimum common string partition problem arises in string comparison and in models of genome rearrangement, where…