# LeetCode Longest Palindromic Substring: DP vs Linear Approach

## Overview

LeetCode Longest Palindromic Substring: Different DP formulas are given to tackle this problem and there even exists linear time approach.

## LeetCode Longest Palindromic Substring

Given a string *S*, find the longest palindromic substring in *S*. You may assume that the maximum length of *S* is 1000, and there exists one unique longest palindromic substring.

## Solution and **Precautions**: DP vs Linear Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
string gao(const std::string & strInput) {
string strResult("");
if(strInput.size() == 0)
return strResult;
bool isSymmentricString[1005][1005];
memset(isSymmentricString, 0, sizeof(isSymmentricString));
int iStringLength = strInput.size();
int iMaxStartIndex = 0;
int iMaxSymmtricStringLength = std::min(1, iStringLength);
for(int i = 0; i < iStringLength; ++i)
for(int j = i; j >= 0; --j)
isSymmentricString[i][j] = true;
for(int len = 2; len <= iStringLength; ++len) {
int iEndIndex = -1;
for(int iStartIndex = 0; iStartIndex + len <= iStringLength; ++ iStartIndex) {
iEndIndex = iStartIndex + len - 1;
if(strInput[iStartIndex] == strInput[iEndIndex] &&
isSymmentricString[iStartIndex + 1][iEndIndex - 1]) {
iMaxSymmtricStringLength = len;
iMaxStartIndex = iStartIndex;
isSymmentricString[iStartIndex][iEndIndex] = true;
}
}
}
return strInput.substr(iMaxStartIndex, iMaxSymmtricStringLength);
}
string longestPalindrome(string s) {
return gao(s);
}
};

Update on Feb 2, 2015, the following java code can pass the LeetCode OJ for this Longest Palindromic Substring as well:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n <= 1)
return s;
boolean [][] dp = new boolean[n][n];
for (int i = 0; i < n; ++i)
for (int j = i; j >= 0; --j)
dp[i][j] = true;
int maxLength = 1;
int maxStart = 0;
for (int len = 2; len <= n; ++len) {
for (int i = 0, j = i + len - 1; j < n; ++i, ++j) {
if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {
dp[i][j] = true;
maxLength = len;
maxStart = i;
}
else
dp[i][j] = false;
}
}
return s.substring(maxStart, maxStart + maxLength);
}
}

## LeetCode Longest Palindromic Substring, Tips and Divergent thinking:

(1) Be careful of the several points within the source code above, i.e., Firstly, the input might be empty string, that is why we test the size first. Secondly, the initial condition for isSymmentricString[1005][1005] is to set all isSymmentricString[i][j] = true, where j <= i, it is not enough to set only isSymmentricString[i][i] = true. Thirdly, don’t try to copy the string into the final result string to return every time we got a longer palindromic substring, this copy takes O(N) time, which will leads to TLE from the OJ. So everytime we always record the start index and the length, rather than the potential longest palindromic substring.

(2) The three algorithm methods mentioned above for solving Longest Palindromic Substring problem are what I could come up with, there are some other quite thoughtful solutions including the linear time solution which could be found in the following links.

Very good references: “Longest Palindromic Substring Part I” and “Longest Palindromic Substring Part II”

## Summary

LeetCode Longest Palindromic Substring: Different DP formulas are given to tackle this problem and there even exists linear time approach.