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.

P[i][j]

s[i..j]

P

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); }