# JAVA o(n*n). simple, not very fast

• ``````public class Solution {
public String longestPalindrome(String s) {
int n = s.length(), longestBegin =0, maxLen =1;
boolean dp[][] = new boolean[n][n];
for(int i=0;i<n;i++)dp[i][i]=true;
for(int i=0;i<n-1;i++){
if(s.charAt(i) == s.charAt(i+1)){
dp[i][i+1]=true;
longestBegin = i;
maxLen = 2;
}
}
for (int i=n-3; i >=0;i--){
for(int j=i+1; j<n;j++){
if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){
dp[i][j]=true;
if(maxLen< j-i+1) {
longestBegin = i;
maxLen = j - i + 1;
}
}
}
}
return s.substring(longestBegin,longestBegin+maxLen);
}
}``````

• ``````public class Solution {
public String longestPalindrome(String s) {
int n = s.length(), longestBegin =0, maxLen =1;
boolean dp[][] = new boolean[n][n];

for(int i=0;i<n-1;i++){
dp[i][i]=true; // cut previous for
if(s.charAt(i) == s.charAt(i+1)){
dp[i][i+1]=true;
longestBegin = i;
maxLen = 2;
}
}

for (int i=n-3; i >=0;i--){
for(int j=i+2; j<n;j++){ // start from i+2 works well
if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){
dp[i][j]=true;
if(maxLen< j-i+1) {
longestBegin = i;
maxLen = j - i + 1;
}
}
}
}

return s.substring(longestBegin,longestBegin+maxLen);
}
``````

}

• could you get a AC?

• This post is deleted!

• ``````// dp solution
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int start = 0, max = 0;
boolean [][] dp = new boolean[len][len];
// dp
for ( int i = len - 1; i >= 0; i-- )
{
for ( int j = i; j <= len - 1; j++ )
{
if ( s.charAt( i ) == s.charAt( j ) )
{
if ( i + 1 > j - 1 )
{
dp[i][j] = true;
} else if ( dp[i + 1][j - 1] == true )
{
dp[i][j] = true;
}
if ( dp[i][j] == true &&  j - i + 1 > max )
{
start = i;
max = j - i + 1;
}
}
}
}
return s.substring( start, start + max );
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.