Need help in Counting string problem

could someone help me where my logic is going wrong

where dp[i] indicates the answer to the string from s[i] to the end of the string .

my solution https://www.codechef.com/viewsolution/11564405

I think you haven’t got the question right. So I will try to put it simple here :

Requirements :

find all strings t

  1. t is lexicographically larger than the given string.

  2. When both reversed, t is still larger than the given string.


Observation :

  1. lexicographical comparison works in a straight forward manner that is, start from the first, until you find one char larger than the other. The string with the larger char will be larger. So this suggests that just making any one char larger, no matter what characters follow it in the string, will make the string larger.

  2. But it should be larger when reversed too. So choose any two characters and make them larger, without even bothering what are the characters between those two chosen chars.


Working :

given a string “B C D E F G H I J K”

Choose any two of them and make them larger (can be made in “‘Z’- that char” ways). While allowing all the character in the middle of those two to be whatever they want.

 String                    :  B    C    D    E     F    G     H     I     J      K
 Chosen char               :            ^                     ^
 Ways they can be changed  :           22   26    26   26    18

so for this case ans would be 22 x 26 x 26 x 26 x 18

And the final ans will be summation of all such cases. ( and all cases where only one character is changed.)


Conclusion:

What you are doing in your code is different from this and its just multiplying all the numbers.

Hope this helps.

Please read editorials.