Solution to LeetCode Longest Palindromic Substring problem.
Let P[i][j] be true iff the substring s[i..j] is a palindrome. The array P can be computed in \(O(n^2)\) time. Then, we can traverse this array and find the longest palindromic substring.
public String longestPalindrome(String s) {
int N = s.length();
boolean[][] P = new boolean[N][N];
for(int i = N-1; i >= 0; i--){
for(int j = 0; j < N; j++){
if(j <= i) P[i][j] = true;
else P[i][j] = P[i+1][j-1] && s.charAt(i) == s.charAt(j);
}
}
int max = Integer.MIN_VALUE;
int a = 0;
int b = 0;
for(int i = 0; i < N; i++){
for(int j = i; j < N; j++){
if(P[i][j]){
int val = j-i+1;
if(val > max){
a = i;
b = j;
max = val;
}
}
}
}
return s.substring(a,b+1);
}