PROBLEM LINK:Practice Setter: Pranjal Rai DIFFICULTY:Easy PREREQUISITES:Greedy and Basic Math would do. PROBLEM:Given a string $S$ consisting of uppercase characters only, you are to find out the minimum number of characters to change so as to make the string balanced. A string is balanced if all distinct characters present in string occur the exact same number of times. QUICK EXPLANATION
EXPLANATIONSuppose in final string, each character occurs $F$ times and there are $C$ distinct characters present in the string. It can be seen that the length of such string is $C*F$. But we never change the length of the string. So, We need to consider only those values of $C$ and $F$ such that $C*F = S$. Also, we cannot have more than 26 distinct characters, so constraint $1 \leq C \leq 26$ hold. So, let's check each value of $C$. If $S \bmod C \neq 0$ the string cannot be balanced using $C$ distinct characters, so ignore such values of $C$. Otherwise, the balanced string shall contain $S/C$ occurrences of each of distinct $C$ characters. The question here is, who to identify which character to change? To understand this, instead of changing the minimum number of characters, let us preserve the maximum number of characters. We can see, that we can choose any of the distinct $C$ characters present, and preserve at most $F = S/C$ occurrences of each chosen character. It makes sense to choose the characters with maximal frequencies and try to preserve maximum characters. If we sort the character frequencies in decreasing order, it can be seen that its optimal to choose first $min(C, D)$ ($D$ denote the number of distinct characters in initial string) characters and for each of these characters, preserve $min(f, S/C)$ characters. The letters not preserved need to be replaced. Hence, we can check for each value of $C$ which gives the minimum number of characters to be changed and print this minimum number of characters to be changed. Time ComplexityThe time complexity is $O(S+A*log(A))$ per test case where $A = 26$ is the size of the alphabet. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Feb, 23:43

The Setter's Solution, Tester's Solution, and Editorialist's Solution aren't visible. :( answered 19 Feb, 11:19
