Printing the Longest Palindromic Substring (LPS)

Question

I'm learning DP for myself and I could solve the length of longest palindromic substring easily, but having a hard time to actually print the longest palindromic substring. I checked a video LINK where he shows a way to get the LPS but I can't get it to work for longer sequences. Consider the example from geeksforgeeks:

S: forgeeksskeegfor

Now in my approach I'm filling up the bottom triangle of the table like in the order of:

for (int i = 1; i < dp.length; ++i)
    for (int j = i-1; j >= 0; --i)
        dp[i][j] = (s[i] == s[j]) ? 2+dp[i-1][j+1] : Math.max(dp[i][j+1], dp[i-1][j])

So for the above string my DP table looks like:

      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
      f  o  r  g  e  e  k  s  s  k  e  e  g  f  o  r
 0 f  1
 1 o  1  1
 2 r  1  1  1
 3 g  1  1  1  1
 4 e  1  1  1  1  1
 5 e  2  2  2  2  2  1
 6 k  2  2  2  2  2  1  1
 7 s  2  2  2  2  2  1  1  1
 8 s  2  2  2  2  2  2  2  2  1
 9 k  4  4  4  4  4  4  4  2  1  1
10 e  6  6  6  6  6  6  4  2  1  1  1
11 e  8  8  8  8  8  6  4  2  2  2  2  1
12 g 10 10 10 10  8  6  4  2  2  2  2  1  1
13 f 12 10 10 10  8  6  4  2  2  2  2  1  1  1
14 o 12 12 10 10  8  6  4  2  2  2  2  1  1  1  1
15 r 12 12 12 10  8  6  4  2  2  2  2  1  1  1  1  1

This is the transpose of the original matrix from the video an in turn I don't need to separately handle len 1,2,>=3 length of palindrom subsequences. The problem either way is the same whatever method I go for. So the length of the longest palindromic subsequence is at dp[15][0] := 12 which is correct. The problem is the tracing back...

12 => dp[15][0] => s[0] != s[15], now which way I go... I the video he goes on max of the next or top elements but for longer strings those might be equal. So, let's suppose I go upwards and nor 'f' neither 'r' are part of the LPS.
12 => dp[14][0] => s[0] != s[14]
12 => dp[13][0] => s[0] == s[13] => LPS: f[..........]f (At this point I go diagonally)
10 => dp[12][1] => s[1] != s[12] At this point I would start to go up as before but if I do that I won't get the LPS, so I have to go right
10 => dp[12][2] => s[2] != s[12] Still going right
10 => dp[12][3] => s[3] == s[12] => LPS: fg[........]gf
 8 => dp[11][4] => s[4] == s[11] => LPS: fge[......]efg
 6 => dp[10][5] => s[5] == s[10] => LPS: fgee[....]eefg
 4 => dp[ 9][6] => s[6] == s[ 9] => LPS: fgeek[..]keegf
 2 => dp[ 8][7] => s[7] == s[ 8] => LPS: fgeeksskeegf
 0 DONE

So the question is, why did I switch direction from going upwards to going right after I found a match at dp[13][0]? The same happens if I start going right I find I match I can't continue to go right nor can decide based on the max value of the cells as they might be equal. For short strings sure that works as in the example in the linked video but that's about it. Longer string equal adjacent cells then which way do I go?

Yonlif Yonlif · Accepted Answer · 2020-01-03T12:28:51

In order to perform back tracing in DP you need to remember where you came from. Generally this means that The memory will now increase to O(N ^ 2) even though you could have done it in O(N).

The reason we go from [12][1] to [12][2] and not to [11][2] is that if you were doing the calculation - the value of [12][1] will be determined from [12][2] since the letters are not equal and it is the maximum. That is the reason we are going right - it was the cell that determined this cell value. In all the other cases it didn't really matter that much since the values were equal so you could go right or up.

Printing the Longest Palindromic Substring (LPS)

1 Answers