Problem statement

https://binarysearch.com/problems/Foo-Bar-Qaz-Qux/

Solution

First of all if all values are the same, we can not do any steps. Also we have invariant: count(R) - count(B) and count(B) - count(G) will not change their values modulo 2. It means that if we have say odd, odd, odd, then we can have in the end odd, odd, odd or even, even, even. Because we can not have 0 in the end, the minimum value we can have is 2 in this case. This was an estimate, how about example?

The key insight is that, if you have 4 contiguous quxes and not all of them are equal, you can always transform two of them such that the 3 quxes left are also not equal. In this way we always can reduce problem to 3 quexes and then it can be either 1 or 2.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        r, g, b, n = A.count("R"), A.count("G"), A.count("B"), len(A)
        if r == n or g == n or b == n:
            return n
        else:
            if r % 2 == g % 2 == b % 2:
                return 2
            else:
                return 1