Chef has N rooms which are either painted in red or blue or green color.He wants to repaint minimum number of rooms so as to have same color in each room.
We need to paint all other rooms in a color which is painted in maximum number of rooms.
In order to find minimum number of rooms to be repainted, we first need to find count of each color in rooms. You can either use three different variables to store count of three different colors (i.e. red, blue and green) or you can simply use an array of size 3 (a) and initialize it with zero. In this editorial i am explaining the later one. You can store the count of each color in array by traversing the given string ( for e.g. Check first character of the string , if it is ‘R’ increase value of a by 1 , if it is ‘B’ increase value of a by 1 or if it is ‘G’ increase value of a by 1 and do this for the next N-1 characters of string). After this sort the array , you can do this easily by using inbuilt sort() function of C++ Standard Template Library (STL). So, now you know the count of different colors ( but you don’t know which count is for which color as it might have changed after sorting, don’t worry you don’t even need that ) a has the count of the color which is painted in maximum number of rooms , so minimum number of rooms we need to paint are a + a.
My solution link : https://www.codechef.com/viewsolution/26814735
CODESTAR’S EDITORIAL : 1