*I didn’t participate in the SRM, but solved this problem later. What follows is strictly a personal account of my attempt to this. I tried to be elaborate to make this accessible to newcomers. Hoping people facing difficulty in solving this problem may find this post helpful. My blog revives with this post!*

**The problem**

Problem statement (requires login)

Excluding the unnecessary details, the problem statement reduces to:

Given a string *chocolates[]* and an integer *maxSwaps*, and you are allowed to swap any two adjacent elements of the string. Return length of the longest substring of identical characters achievable by no more than **maxSwaps** swaps.

**First thoughts**

Observing the sample cases, I devised a trivial one: AAABCAA. In this case BC is sandwiched between two segments of A’s. With 4 swaps, we can move BC to the right, and get the string AAAAABC. Also, 4 is the optimal number of swaps required to get a longer substring of identical characters from the given string.

Up to this point observation confirmed that, *joining segments of identical characters is the only way to produce longer segments. *But, how to join them with minimum possible swaps? For trivial cases like AAABCAA, solution is quite obvious—moving all sandwiched characters to either left or right whose length is shorter, a greedy approach. But, what about cases with more than two segments of identical characters, like AAABCABBACAA? What kind of complication do they introduce? Still no idea. Once I am with an idea how to do this, the rest is simple—for all possible substrings of **chocolates[]** flanked by segments of identical characters, find the minimum number of swaps (**swap**) needed to take all characters not identical to flanks’ out, if **swap** **minSwaps **take the maximum of the lengths among all such substrings of identical characters obtained.

Continue reading →