Approximating reversal distance for strings with bounded number of duplicates

For a string A=a1…anA=a1…an, a reversal  ρ(i,j)ρ(i,j), 1⩽i⩽j⩽n1⩽i⩽j⩽n, transforms the string A   into a string A′=a1…ai-1ajaj-1…aiaj+1…A′=a1…ai-1ajaj-1…aiaj+1…anan, that is, the reversal ρ(i,j)ρ(i,j) reverses the order of symbols in the substring ai…ajai…aj of A  . In the case of signed strings, where each symbol is given a sign ++ or --, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k   times in each string, for some k⩾1k⩾1. The main result of the paper is an O(k2)O(k2)-approximation algorithm running in time O(n)O(n). For instances with 3