KLPM - Editorial



can anyone suggest me more dp questions for practise


Then we have that D[i,j] = 1 + D[i+1,j-1] + LR[i+1,j-1] + RL[i+1,j-1] when S[i] = S[j], 0 otherwise.
i didn’t get the logic behind this line, can you please elaborate


Thank you! Aniket. Awesome Explanation!


This problem is really amazing. Any more problems like this for practice?


Nice solution! Your insight is penetrating.


mafia 99 i had the same approach as well… however u can optimize the solution if you create 2n+1 places corresponding to centres of each probable palindrome… however that’s a story for another day…


hey, i am confused with array P. can you tell me explain me??


By far the best explanation and easiest to follow through with code. Thanks a ton. A life saver for noobies like me.


I am sorry, but couldn’t understand a thing in the tutorial. Please let it be in simple words and with more explanation with examples. Everyone reading it isn’t a 4star or 5star coder. It is defeating the whole purpose of tutorials if the beginners can’t understand it. Thank you. :slight_smile:


Thank you. That cleared up a lot of doubts.


Hey @surprised1 thank you for the explanation.
I have read your solution, its an extremely neatly written code. But a few things are still foggy.
Can you please explain this part of your code, I mean, what exactly are you doing here?

for (float pivot = 0; pivot < l; pivot += .5) { 
    float palindromeRadius = pivot - (int)pivot; 

while ((pivot + palindromeRadius) < l && (pivot - palindromeRadius) >= 0 && str[((int)(pivot - palindromeRadius))] == str[((int)(pivot + palindromeRadius))]) {   
    dpP1[(int)(pivot - palindromeRadius)][(int)(2*palindromeRadius + 1)]++;
    dpP2[(int)(pivot + palindromeRadius)][(int)(2*palindromeRadius + 1)]++;

for(int i=0; i<l; i++) {
		for(int j=1; j<l; j++) {
			dpP1[i][j] += dpP1[i][j-1];
			dpP2[i][j] += dpP2[i][j-1];

What is the use of pivot, palindromeRadius and why are they float and being incremented by 0.5?
Why are we adding dpP1[i][j] to dpP1[i][j-1] and same for dpP2?

I am unable to understand this, but I really want to. Because maybe this is some new type of solution which I am unable to understand but really want to.

Thank you for all the help. :smile:


Thanks a lot. Really helpful explanation. And easy to follow code.


thanks, it really helped :+1:


@aniket_sanghi thanks for this explanation. So many people have explained their solutions and i understood none of them, i was on the verge of quitting this problem.


Most valuable question is what are these A, B and C in S in the explanation before reading further? @admin


The following link is not working. Please share the working link.


@vijju123 Hi. :stuck_out_tongue: