# 2 ways of solving this problem(JAVA) - O(n^2) & O(n^3)

• Brute Force - O(n^3) // haven't tried but mostly won't be accepted

``````public String LongestPalindrome(String s){
int max = 1;
int front = 0;
String ans = "";
int back = s.length() - 1;
while(front < s.length() - 1){
while(back > front){
String current = s.substring(front,back+1);
if(isPal(current) && (current.length() > max)){
ans = current;
}
back--;
}
front++;
back = s.length() - 1;
}
return ans;
}
public boolean isPal(String s){
int i = 0, j = s.length() - 1;
while(i < j){
if(s.charAt(i) != s.charAt(j))
return false;
i++;
j--;
}
return true;
}
``````

Dynamic Programming - O(n^2)

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

}
}
``````

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