KLPM - Editorial

editorial
, , ,
22

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

23

Thank you! Aniket. Awesome Explanation!

1 Like
24

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

25

Nice solution! Your insight is penetrating.

26

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…

27

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

29

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

1 Like
30

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:

1 Like
31

Thank you. That cleared up a lot of doubts.

32

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)]++;
    palindromeRadius++; 
	}
} 

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:

33

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

1 Like
34

thanks, it really helped :+1:

1 Like
35

@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.

2 Likes
36

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

1 Like
37

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

39

Aren’t there going to be repetitions involving the three cases?