# Share my concise thinking process with a special idea.

• ##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;
``````