PROBLEM LINK:
Author: Mayur Gajabi
Tester: Md Shakim
Editorialist: Mayur Gajabi
DIFFICULTY:
EASY
PREREQUISITES:
Ad-hoc
PROBLEM:
You are given a String of length N containing only characters a,b and c. In one operation you are allowed to change any character in the string to any other character. You have to make the string repititve with a period of K in minimum number of operations.
EXPLANATION:
For string to be k periodic, elements 1, k + 1, 2 * k + 1, … must be equal. Also, elements 2, k + 2, 2 * k +2, … must be equal. And so on up to k. So each character of the string is a part of exactly one group. And there are k groups total. Each such group is independent.
Let’s consider some group of elements, that contain p ‘a’ and q ‘b’ and r ‘c’. All elements in this group must be same. So we either change all characters to either a,b or c. For the optimal solution, you should select the operation with smaller number of changing operations required. So the character with the highest frequency in these group should be kept and 2 others character should be changed to it.
Hence there are 3 cases :
(i) p>=q>=r or p>=r>=q:- In these case it is better to change all characters to ‘a’,thus the minimum number of operations required will be q + r.
(ii) q>=p>=r or q>=r>=p:- In these case it is better to change all characters to ‘b’,thus the minimum number of operations required will be p + r.
(iii) r>=p>=q or r>=q>=p:- In these case it is better to change all characters to ‘c’,thus the minimum number of operations required will be p + q.
TIME COMPLEXITY
O(N)