612 - DNA Sorting
We have to sort a group of equal length strings by their inversion count. An inversion is an out of order pair, or more formally, the inversion set of an array is the set of pairs and . Since the strings are relatively short, a simple check all pairs solution will suffice to count the number of inversions in each string. Remember that we need to break ties by keeping things in order, so a stable sort is required.
Since the string alphabet is so small, consisting of only 4 symbols, A, C, G, and T, we can do the inversion count in time with a dynamic programming algorithm. We maintain a 4 by n array that keeps track of at index i how many occurances of each character there are after the ith character in the string.
In C++, the STL's stable_sort can be used to considerably improve coding time.
10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT
CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA