Codeforces Round #630 (Div. 2) Problem C

Problem link : https://codeforces.com/contest/1332/problem/C

So the problem is basically constructive and involves observation.

Here we have 2 restrictions

1) The string should be a palindrome

2) s[i] == s[i + k]

Let's make some observations using 2nd condition

as s[i] == s[i + k] , this basically means there will be same blocks of size k repeated n/k times.
Also n is divisible by k so there is no problem.

See this in the figure above.

But now see how we violate the first condition of palindrome.

s[i] should be equal to s[n - i].

If you think about it a bit you will find out that the small block k should itself be a palindrome !!

This is the main observation, after this it's easy to solve.

So basically the palindrome positions of the smaller block of size k = 3 should be fixed and rest of the blocks should also have same value.

So we are in a way restricted to keep values of i = j,j + k,j + 2*k, ... for all j = 0 to k -1 same and make the small block as palindrome.

So greedy intuition says don't replace the letter which has occurred most in some position and change others to this letter. So you accumulate all the letters into one block of size k and then accumulate for positions s[i] and s[k - 1 - i] in this block and then choose the letter which has occurred the most.

Submission Link : https://codeforces.com/contest/1332/submission/75153656