# longest palindrom

Dynamic programming solution, O(N2) time and O(N2) space: To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:

P[ i, i ] ← true P[ i, i+1 ] ← ( Si = Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

This gives us a run time complexity of O(N2) and uses O(N2) space to store the table.

Note: the above from http://www.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

```public static string LongestPalindrom(string str)
{
if (str == null || str.Length < 2)
{
return str;
}

int longestIndex = -1;
int maxLen = -1;
bool[,] table = new bool[str.Length,str.Length];
for (int i = 0; i < str.Length; i++)
{
table[i,i] = true;
longestIndex = i;
maxLen = 1;
}

for (int i = 0; i < str.Length - 1; i++)
{
if (str[i] == str[i + 1])
{
table[i,i + 1] = true;
longestIndex = i;
maxLen = 2;
}
}

for (int len = 3; len <= str.Length; len++)
{
for (int i = 0; i < str.Length - len + 1; i++)
{
int j = i + len - 1;
if (str[i] == str[j] && table[i + 1,j-1])
{
table[i,j] = true;
longestIndex = i;
maxLen = len;
}
}
}

return str.Substring(longestIndex, maxLen);
}```