The most important observation here is that similar characters must be together. I want to ask people who solved it by themselves reached to that observation ? It was asked by codebuster_10 here but no one replied. Editorial gives the mathematical proof but I want to know the lane of thought (because first we make guess and then justify).
Also it will be good if someone provides easier way of justifying it.
As with most greedy algorithms, you make a guess and then justify it later (or simply submit and don't justify it).
I think it is easier to see this if the input string consists of only 2 distinct characters.
Suppose the input has length $$$n$$$, and consists of 1s at positions $$$x_1, x_2, \ldots, x_k$$$ (in increasing order), and we output a binary string consisting of 1s at positions $$$y_1, y_2, \ldots, y_k$$$ (in increasing order). Then the number of swaps is $$$\sum |x_i - y_i|$$$. By convexity argument you want to put all $$$y_i$$$ in front, or all $$$y_i$$$ at the back.
Can you elaborate on what a convexity argument is?
same doubt!!
Suppose $$$y_1, y_2, \ldots, y_{i-1}, y_{i+1}, \ldots, y_k$$$ are fixed, and we want to choose the best possible $$$y_i$$$.
We want the $$$y_i$$$ that maximizes $$$|x_i-y_i|$$$, subject to the constraint $$$y_{i-1} < y_i < y_{i+1}$$$. Then we must have $$$y_i=y_{i-1}$$$ or $$$y_i = y_{i+1}$$$. So the $$$y_i$$$ must "stick" together.
I made a brute force solution and checked for different cases with length less than 10. After that I knew what to do with just a little bit of optimisation.
My intuition was to greedily increase the number of inversions. So I was constructing the answer, At the 0th index, I greedily chose the character that was farthest from the 0th index, then did the same for the 1st index, and so on. You take any test case, this approach will give you a string with all similar characters together. Once you observe this, it is easy to notice that we can check all possible cases.
You can check this Explanation
My intuitive justification was that if we consider having some pattern "xyx" in our answer, then this is clearly not optimal because either the corresponding "x"s both occur before the corresponding "y" in the original string, in which case we shouuld instead have "yxx" to maximize the number of inversions, or it's the oppossite in which case we should have "xxy", or it's actually "x..y..x" in the original string in which case both "yxx" and "xxy" would be better.
Given that we never want to have "xyx" in our answer, we can just nonrigorously generalize to say that we never want to have "x..y..x" in our answer either, leading to the solution.