Minimum number of swaps needed to 'group' a sequence? Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for any $i<k<j$. For example, $\{a,a,c,c,c,b,b\}$ is grouped, where as $\{a,b,a,c,c,c,b\}$ is not. 
What is the minimum number of swaps needed to make a given sequence $s$ 'grouped'? Is the computational complexity (in terms of the length of the string and the size of character set) of this problem known in literature? 
A practical motivation might stem from (not completely sure though) the process of "disk de-fragmentation", where 'pieces' of the same file are grouped together in contiguous memory segments. . 
 A: Well, obviously any sorting algorithm can achieve what you want, since if the entries in the sequence are sorted (under whatever arbitrary linear order you impose) they have the grouping property.
Given $N,$ there are sorting algorithms with complexity $O(N \log N).$ These algorithms make no assumptions about the values they are sorting.
However, you can do better, depending on the relationship of the alphabet size $M$ to list length $N$. In particular, you can map your alphabet to $\{1,2,\ldots,M\}$ and thus assume that the values to be sorted are all nonnegative and bounded by $M.$
In that case, the counting sort algorithm can sort your sequence with time complexity $O(N+M).$ Alternatively, you can use radix sort with complexity $O(w N),$ where $w$ is the number of bits required to store the values you are sorting, so $w=O(\log K).$
A: This is a sorting problem. The sorting algorithm that performs the minimum possible number of swaps in the worst-case scenario is selection sort, with $n-1$ swaps. Its time complexity is $O(n^2)$.
There are of course sorting algorithms that have lower time complexity, such as counting sort and merge sort, but they are irrelevant to the question because they do not rely on swapping items.
A: The answers so far aren’t really addressing the question as asked. This is mainly a reformulation and a few simple observations.
First consider , for a fixed $N,k$ a graph with $\binom{N}k$ vertices labelled by the strings made of $k$ a’s and $N-k$ b’s. Each vertex has degree $k(N-k)$ with an edge to each string which results from swapping an a and a b. There are two distinguished vertices, $k$ a’s then $N-k$ b’s and the reverse.
Q: Given a particular vertex find the closest distinguished vertex and a path to it. The computational complexity matters  but swaps are expensive. So it is really a question of finding the absolute minimum number of swaps.
In this case the distance between two strings is half the number of places they differ, i.e. half the Hamming distance. So find which of the two is closest and an optimal sequence of swaps should be clear.
I suppose the sequence $aaabbbaaa$ takes $3$ swaps and generalizes to $\frac{N}3$ swaps. Is that the worst case? 
In case $N=2k$ is $ababab\cdots$  taking about  $\frac{N}4$ swaps worst?
I general we have all length $N$ sequences resulting from a certain multiset with $M$ distinct characters. The number of these is given by a certain multinomial coefficient. There are $M!$ sorted sequences so we might not want to consider them all. The Hamming distance gives some bound on the distances but it might not be as simple as in the $M=2$ case.
