Pérez Art Museum Miami

This is a supposedly easy problem that involves finding the minimum number of elements in a list after the adjacent elements have been merged and transformed. Here is the full problem -

On a mysterious island there are creatures known as Quxes which come in three colors: red, green, and blue. One power of the Qux is that if two of them are standing next to each other, they can transform into a single creature of the third color.
Given N Quxes standing in a line, determine the smallest number of them remaining after any possible sequence of such transformations.
For example, given the input ['R', 'G', 'B', 'G', 'B'], it is possible to end up with a single Qux through the following steps:
        Arrangement       |   Change
['R', 'G', 'B', 'G', 'B'] | (R, G) -> B
['B', 'B', 'G', 'B']      | (B, G) -> R
['B', 'R', 'B']           | (R, B) -> G
['B', 'G']                | (B, G) -> R
['R']                     |

Understanding the problem

It is very easy to go down a rabbit hole trying to solve this problem if you skip a line of the problem like I did -

I had decided to use a stack for the solution, however the key sentence that I had missed was -

determine the smallest number of them remaining after any possible sequence of such transformations.

Quite simply 2 elements or 'Quxes' can transform into a single Quxe if they are adjacent to each other.

Depending on the which element we choose to transform there could be totally different outcomes. In the example below, it is possible to arrive at a solution of 3, whereas 1 would have been the minimum.

Solution

This does require a recursive solution where we make all possible choices.

The choice being - which 2 elements to pick to transform first.
Then recurse on the resultant array
Finally, minimize on the results from each choice and return that value

The solution could be improved by memo-izing the input array. Once we have found a minimum result for a sub-array that result will never change.

Alternative Solution

I did come across a very interesting mathematical solution that is based on deduction

https://www.cnblogs.com/lz87/p/11518225.html

It involves looking at the set of elements holistically -

When one group has an odd number of elements and the other 2 groups have an even number of elements (or vice versa) -
- the result will always be 1
When all groups have either odd or even number of elements
- the result will always be 2