#Problem link:

[Practice] #Problem link:

[Practice] Contest Page | CodeChef

[Codeyssey] Contest Page | CodeChef

**Author:** [Abhishek Patnigere] CodeChef User | CodeChef

**Editorialist:** [Akshat Goyal] CodeChef User | 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();

}