We solve this problem for the string "abccbc".

We have already studied how to make a dp array for this problem in the previous question. Let's discuss it again.

We make a 2D array of the dimensions: string length * string length as shown in figure below.

Each cell represents the substring assigned to that cell starting from the corresponding row element and ending at the corresponding column element. Look at the figure below.

Reader, here, when we start with a1 and end with a1, then the substring is "a".

If we start from b2 and end at b5 then we include all the elements in between and the corresponding substring is "bccb". Similarly the other substrings can be found too.

The cells in the lower triangle are empty because their starting element occurs after the ending element and in such cases a substring is not formed.

In the above figure, we have made diagonals across the substrings. We see that across the 0th diagonal, the length of the substrings is 1, across the 1st diagonal the substring length is 2. Across the 2nd diagonal the substring length is 3 and so on.

Now to analyze the substring at any cell, say the cell storing "bccb", we first find the corresponding diagonal (here, 3rd diagonal). As discussed earlier, for the 3rd diagonal, the length of the substring should be 1+3=4.

So we go 4 places back from the corresponding column element (i.e. b2) till the current place (i.e. b5) and print the elements between them.

Or we can go from the current row element (i.e. b2) till 4 places ahead of the current row element (i.e. b5).

Now as in above figure, for a string to be a palindrome, the elements at the extremities (part a) should be equal. Also the inner string (part b) should be a palindrome.

Now we again need to check if the extremities of part b are equal and if the inner string of part b is a palindrome and so on.

Let's see how we can use this.

shows the palindrome substrings marked with a tick and the non palindromic ones marked with a cross.

We discuss a few examples on how to reach this result.

• Since for diagonal 0, the length is only 1, therefore every element is a palindrome.
• Let's move to diagonal 1. As discussed earlier, for "ab", the elements at extremities 'a' and 'b' are not equal, hence it is not a palindrome. Same is the case for substrings "bc", "cb" and "bc". However since, extreme elements are the same in "cc", therefore it is a palindrome.
• Moving to diagonal 2, we again check for the extremities. In this example, since none of the substrings except "bcb" fulfill our requirement, therefore none of them are palindromes.
For "bcb", we now check if the inner string "b" is a palindrome or not. The answer to this is stored in the cell for b5 row and b5 column, which is true, hence "bcb" is a palindrome too.
• Let's check the element "bccb". Here, since the extremities are the same, therefore we move on to the next check. We check if the inner string "cc'' is a palindrome or not. It can be done by checking if the string "cc '' on the antidiagonal is palindrome, which it is as shown by row c3 and column c4. Hence the substring "bccb" is a palindrome too.
• The same process is followed by the other substrings too.

Now for the main part, to print the longest palindrome out of all the substrings, we find the last substring which was a palindrome. Here, we found it for diagonal 3 or length 4. Hence, the desired substring is "bccb".

The code for this problem is quite straightforward and similar to the one we discussed in the previous question. We want you to take help of the code given below if you get stuck anywhere.