11public class Solution {
22public String longestPalindrome (String s ) {
33
4+ char []S =s .toCharArray ();
45
5- // http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
6+ if ( S . length == 0 ) return "" ;
67
7- final char []S =s .toCharArray ();
8- final int N =S .length ;
8+ boolean [][]P =new boolean [S .length ][S .length ];
99
10- if (N ==0 )return "" ;
11- if (N ==1 )return s ;
12- if (N ==2 )return S [0 ] ==S [1 ] ?s :"" ;
10+ int maxi =0 ;
11+ int maxlen =1 ;
1312
14- boolean [][]P =new boolean [N ][N ];
13+ // len 1
14+ Arrays .fill (P [1 -1 ],true );
1515
16- for (int i =0 ;i <N -1 ;i ++){
17- P [i ][i ] =true ;
18- P [i ][i +1 ] =S [i ] ==S [i +1 ];
19- }
20-
21- P [N -1 ][N -1 ] =true ;
22-
23- for (int j =2 ;j <N ;j ++){
24- for (int i =0 ;i <j ;i ++){
25- P [i ][j ] |=P [i +1 ][j -1 ] &&S [i ] ==S [j ];
16+ // len 2
17+ for (int i =0 ;i <S .length -1 ;i ++){
18+ if (S [i ] ==S [i +2 -1 ]){
19+ P [2 -1 ][i ] =true ;
20+ maxi =i ;
21+ maxlen =2 ;
2622 }
2723 }
2824
29- int mi =0 ;
30- int mj =0 ;
31-
32- for (int i =0 ;i <N ;i ++){
33- for (int j =0 ;j <N ;j ++){
34- if (P [i ][j ] && (j -i >mj -mi )){
35- mi =i ;
36- mj =j ;
25+ // len 3 to max
26+ for (int len =3 ;len <=S .length ;len ++){
27+
28+ for (int i =0 ;i <S .length - (len -1 );i ++){
29+
30+ if (P [len -1 -2 ][i +1 ] &&S [i ] ==S [i +len -1 ]){
31+ P [len -1 ][i ] =true ;
32+ maxi =i ;
33+ maxlen =len ;
3734 }
3835 }
39- }
36+ }
4037
41- return new String ( S , mi , mj - mi + 1 );
38+ return s . substring ( maxi , maxi + maxlen );
4239 }
43- }
40+ }