Given an array where each number represent a color. After iterating each item in the array (for each item in the iteration the pointer can also point to the second-item-to-the-right), and the two colors in the iteration is the same, do the following checking:
If there is a different color between the pointed colors, the colors will "dissolve" (which is not allowed).
[1,2,1] is not allowed but
[1,1,2,2] is allowed. Here is an explanation for the above test cases:
[1, 2, 1] ^ ^
We find that the two pointed items have the same color. We then realize that the color between the pointed items are different than the two same colors; this ensures a "dissolving".
The following is an explanation of the second example:
[1, 1, 2, 2] ^ ^
In this step, the atoms are different, so we don't perform the check.
[1, 1, 2, 2] ^ ^
In this step the atoms are still different. All colors do not "dissolve", ensuring a valid array.
We can change one color to another but the condition is if we change one color, then we have to change all of its occurrences in the array. The cost of changing color is the number of appearances of the color in the array.
eg.: if the array is
[1,2,1,2,1,3,2] and we have decided to change 2 to 1, then our array will become
[1,1,1,1,1,3,1] and the cost will be 3 (for changing three 2's to 1's)
We have to minimize the cost and make sure no color dissolves.
[1,1,3,3,2,2] -> 0 (no changes are required to prevent dissolving) [1,3,1,3,1] -> 2 (change all 3's to 1's costs 2) [1,1,2,3,2,3]-> 2 (change color of all 2's to 3's OR change color of all 3's to 2's) [1,2,2,2] -> 0 (This is valid; in the second iteration, the color between the pointed colors are equal to the pointed colors.) [1,2,1,2,1,3,2] -> 3 (the 1's must be changed to make the array valid, and there's 3 of them)