Transforming strings by exchanging elements at bounded distance is applicable in fields like molecular biology, pattern recognition and music theory. A reversal of length two at position i is denoted by (i i+1). When it is applied to π, where π = π 1,π 2, π 3,..., π i ,π i∈+∈1, π n , it transforms π to π′, where π′ = π 1,π 2, π 3,..., π i∈-∈1,π i∈+∈1, π i , π i∈+∈1, ..., π n . We call this operation an adjacent swap. We study the problem of computing the minimum number of adjacent swaps needed to transform one string of size n into another compatible string over an alphabet σ of size k, i.e. adjacent swap distance problem. O(nlog 2 n) time complexity algorithms are known for adjacent swap distance. We give an algorithm with O(nk) time for both signed and unsigned versions of this problem where k is the number of symbols. We also give an algorithm with O(nk) time for transforming signed strings with reversals of length up to 2, i.e. reversals of length 1 or 2. © 2008 Springer-Verlag Berlin Heidelberg.
Dr. Bhadrachalam Chitturi, Sudborough, H., Voit, W., and Feng, X., “Adjacent Swaps on Strings”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5092. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 299–308, 2008.