Codeforces round 621 problem C (div 2) help needed

1

hey can anyone help me understand the editorial of this problem with code?
I am not able to get what he is trying to do in the editorial?
problem link: https://codeforces.com/problemset/problem/1307/C

Thanks in advance.

2

The first thing to notice is that the secret message can’t be of more than 2 characters.
Let us assume that there was a sub sequence XYZ that occured maximum number of times in the given string. Then I say that the string XY occurs at least the same number of times as that of XYZ, plus it may occur independently. So the answer is always of 2 or less characters.

Now checking single character answers are easy, just check for every 26 characters, how many times they occur.

To check the sub sequences of length 2, you should observe that you can take any 2 characters from the string and their indexes would form an AP. So you just need to check for every pair of characters, how many times they occur in the string.

You can do that by keeping a count of how many times a given character occurs after a given index using a 2D dp. Here dp[i][j] represents how many characters are ‘a’+j after index i.

Then you can easily check for all 26x26 pairs how many times they occur.

Here is my Code for reference!

3

Thanks for your explanation , now I got it.