##Prerequisites: Longest common substring (LCS)

For string a and b, their LCS is the longest common substring in both a and b.

For example, for "abcda" and "bcea", the LCS is "bc".

##Solution

Keeping LCS in mind, **the longest palindromic substring of string s is, in fact, the LCS of s and its reversed string**.

For example, lets say `s = "cabbad"`

. Then its reversed string is `s_rev = "dabbac"`

.

The LCS of `s`

and `s_rev`

is "abba", obviously. **Note that this is also the longest padlindromic substring of s**.

Therefore, all we have to do is just finding the LCS of `s`

and `s.reverse()`

. This can be solved by DP.

Take `s1 = "cabbad"`

and `s2 = "dabbac"`

as example. To find the LCS of `s1`

and `s2`

, we use `table[i][j]`

to denote the length of the LCS of `s1.substring(i)`

and `s2.substring(j)`

.

For example, `table[4][4] = 3`

. Because `s1.substring(4)`

is "cabb" and `s2.substring(4)`

is "dabb", and the length of their LCS is `len("abb") = 3`

.

So, the math idea is simple:

```
if s1[i-1] != s2[j-1]
table[i][j] = 0
else
table[i+1][j+1]=table[i][j]+1
```

(Note that table[i][j] should all be initialized to zero first.)

Along with building the `table[i][j]`

, record the max length and its position (`flag`

).

When all the process is finished, the longest palindromic string is `a.substring(flag-max_len, flag)`

.

Here's my Java code:

```
public String longestPalindrome(String s) {
StringBuilder rev = new StringBuilder(s);
String s_rev = rev.reverse().toString();
if(s_rev.equals(s))
return s;
return longestCommonSubString(s, s_rev);
}
public String longestCommonSubString(String a, String b){
char[] sb1 = a.toCharArray();
char[] sb2 = b.toCharArray();
int[][] table = new int[a.length()+1][b.length()+1];
int flag = 0, max_len = 0;
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if(sb1[i-1] == sb2[j-1]){
table[i][j] = table[i-1][j-1] + 1;
if(table[i][j] >= max_len){
max_len = table[i][j];
flag = i;
}
}
}
}
return a.substring(flag - max_len, flag);
}
```

In case of some extreme data like "aaaaa......aaaaa", I use the following code to avoid LTE.

```
StringBuilder rev = new StringBuilder(s);
String s_rev = rev.reverse().toString();
if(s_rev.equals(s))
return s;
```

Hope my sharing can help you :)