CHEFSTRI - Editorial

editorial
, , , ,
1

#Problem link:
[Practice] #Problem link:
[Practice] CodeChef: Practical coding for everyone
[Codeyssey] CodeChef: Practical coding for everyone

Author: [Abhishek Patnigere] stingray8041 | CodeChef User Profile for Abhishek Patnigere | CodeChef
Editorialist: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef

DIFFICULTY: MEDIUM
# PREREQUISITES: Math, Strings

Problem with explanation:

So The Problem asks us to convert our current string to a power of any string with a given power K.

  • So what is a power of a string it is like multiplication of a number say 3^4= 3.3.3.3 . Similarly power of a string can be understood as say we have a string abc so the kth power of our string will be abc concatenated k times with itself. So say S=“abc” is our string than s to the power k where k=4 than our required string is abcabcabcabc.
  • Now what we have to do is we are given a string and we need to convert it to a power of “any” string with a given K. And for this we can only replace characters.
  • So what we have to do is say we have a string of length=12 & K=4. Than we have to make our string repeat 3 characters. Say our initial string is abcbcdabcabd.
  • The logic here is that we need to calculate the count for each character position of each substring of length=3 . So here we have 4 substrings abc,bcd,abc,abd.
  • Now to find the minimum number of replacements we use the greedy approach and find that at each position which character is occuring the most times and subtract it from k we do this for each letter of substring. This will give us the minimum number of replacements required.
  • So for our current string we need to understand that final string is a repetition of a string of length 3.
  • So for position 1 in each of our substring abc,bcd,abc,abd we have 3 a’s and 1 b’s so best way is to change b to a so our replacement count is now=1.
  • For position 2 in each of our substring abc,bcd,abc,abd we have 3 b’s and 1 c so best bet is to replace c to b so our replacement count is now=2…
  • For position 3 in each of our substring abc,bcd,abc,abd we have 2 c’s and 2 d’s so we can replace either so 2 replacements so our replacement count is now=4.
  • And 4 is our final answer. To do this we can either create a map or a array and keep count of each character and subtract the maximum count of character from k we do this for each position and get the answer.

#Solution:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(x) x.begin(),x.end()

void solve() {
string s;
cin >> s;
int k;
cin >> k;
int n = s.size();
ll ans=0;
vector freq(26,0);

int len_copy = n/k;
ll mx=-1;

for(int i=0; i<len_copy; i++) {

  for(int x=0; x<26; x++)
  	freq[x]=0;

  for(int j=i; j<n; j+=len_copy) {
  	freq[s[j]-'a']++;
  }
  mx = *max_element(all(freq));
  ans += k - mx;

}

cout <<ans<<“\n”;

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}