PROBLEM LINK:
Author: Sergey Kulik
Tester: Roman Furko
Editorialist: Balajiganapathi Senthilnathan
DIFFICULTY:
Medium
PREREQUISITES:
Inversions
PROBLEM
Given a string consisting only of r, g and b, we have to find the shortest number of adjacent swaps to group all the similar characters together.
QUICK EXPLANATION
First, observe that all the moves really reduce down to swapping adjacent elements. Try all the 3! = 6 possible ordering of r, g and b. Now since the order is fixed, rearranging the string to a particular order is the same as sorting using the current order. The number of swaps required to sort an array is the same as the number of inversions.
EXPLANATION
Observe that each of the 3 types of moves reduce to swapping adjacent elements in 1 moment of time.
Assume for the moment that we know in which order the final rearrangement should be in. i.e. suppose the ordering is “rgb”, then all the r’s must come first followed by all the g’s and then all the b’s. What is the minimum number of moves required to do this?
Now say s[i] = ‘r’. We know that r comes first, so if there is a ‘b’ or ‘g’ to the left of it, they must be swapped at some time. So, we can count the number of times b or g occur to the left of i and add them to the current answer. Similarly if s[i] = ‘g’ and there is a b to the right of i, then they must be swapped. So we count the number of times g occurs before i and add it to the current answer.
TO generalize, if we know the order o = o_1 o_2 o_3 ( a permutation of r, g and b), we can find the minimum number of swaps to rearrenge the string in that order by looping through the string and keeping a count of the characters of each type we have seen so far. Suppose c_1, c_2 and c_3 are the count of the o_1, o_2 and o_3 seen so far.
We can get the minimum number of swaps as follows:
For i = 0 to len(s) - 1:
-
if s[i] == o_1 cur_ans += c_2 + c_3
-
if s[i] == o_2 cur_ans += c_3
But how do we know which order is optimal? Let us see how many orders are possible. Since there are only 3 possible characters, there are only 3! = 6 possible orderings. So, we can try all possible orders, calculate the minimum number of swaps to achieve that order and take the minimum over all the orders to get the optimal answer.
What we are calculating is the number of inversions in the string given an order.
What is an inversion? Intuitively, it is the number of pairs of numbers which are out of order in the array. More formally, the number of inversions of an array a is the number of pairs i < j such that a[i] > a[j]. We will prove that the number of adjacent swaps required to sort an array is equal to the number of inversions in the array.
Claim:
Minimum number of adjacent swap required to sort an array is exactly equal to number of inversions.
Proof:
By making one adjacent swap, we can not kill more than one inversion.
So the number of swaps required will be at least equal to the number of inversions. So number of inversions will be a lower bound to number of swaps. We can indeed achieve that lower bound as follows.
Process:
-
Pick the minimum element (if there are many, pick the leftmost). All the elements which are on the left side of it should be moved to right side of it. For that you can pick the left adjacent element (if it exists) and swap it with minimum element. Keep repeating this step until minimum element is at the leftmost end. Total number of swaps taken are number of position i’s such that A[i] > A[minPos] and i < minPos where minPos denotes location where minimum element was found. This is nothing but the number of inversions with minPos as one of the index.
-
Now remove the minimum element and repeat step 1.
You can notice that this process will sort the array and minimum number of swaps are exactly equal to number of inversions.
Complexity
There is only one loop and that is run a constant (6) number of times. So the complexity is O(n).