PROBLEM LINK
Author: Vatsal Parmar
Tester: Jaymeet Mehta
Editorialist: Mann Mehta
DIFFICULTY
Easy
PREREQUISITES
DP, Observation, Sorting
PROBLEM
Here all we are given is a string of particular pattern .(Swapping has to be done between the whole blocks of characters with others). The cost of swapping is the difference between the frequencies of the blocks getting swapped.
One can check it in the problem. Our objective is to find the minimum cost to make the string ascending in terms of repetition of characters.
EXPLANATION
To understand this problem lets start this with an example. Consider the string 'aaaaabbbbcccdde'. We know that the final string to attain is 'eddcccbbbbaaaaa'.
First of all its mandatory to find the number of iterations of all given characters and store them into an array. So we can see that the array of frequencies we get is [5(a) 4(b) 3(c) 2(d) 1(e)] in this case. Comparing with the question all we need to do is to convert this array into [1 2 3 4 5] and find the cost to make this conversion.
The simplest way that comes in sight is to swap 1 and 5, so cost is 5-1=4, then we swap 2 and 4, so cost is 4-2=2, thus total cost is 4+2=6.
Now if we take immediate difference of all of our members of given array with the members of sorted array and take their sum we get (|1-5|+|2-4|+|3-3|+|4-2|+|5-1|=12) now as we know that it did both of |4-2| and |2-4| which is meaningless, we get 2 and 4 in position in any one of those two swaps. Same case is with 1 and 5.
Thus we have to divide it by 2 which gives us our final answer.
Now one can think that we can use selection sort in this case but its wrong it brings the smallest in he first place without considering the cost to do it and our job is to find the minimum cost. Thus the immediate difference taken once with its respective element in the sorted array gives us the cost double than the one we require. Now even if we are given an uneven array still it is true for it. Though the case is not like 2-4 and 4-2 like the above case, but the difference aroused due to it is always overtaken by the other element's difference.