This question is quite interesting.

The first method you can comeup with is check every substring, which will take O(n^3) time.

Can we do better? We know that one character is a palindrome itself, we also know that if S[i+1][j-1] is a palindrome and S[i] == S[j], S[i][j] is a palindrome. In this way, we can build up a boolean array dp[i][j] to record if S[i][j] is a palindrome. dp[i][j] = dp[i+1][j-1] && s[i] == s[j].

initilzation, dp[i][i] = true, one char is always a palindrome.

fill up the matrix, this is a little bit tricky because we need dp[i+1][j-1], so outter loop i should start from the largest possible s.length()-2, while inner loop j should start from i to s.length() – 1. Also if j-i == 1 which means two adjacent char, then dp[i][j] = s[i] == s[j]. The code however is quite short:

public class Solution { public String longestPalindrome(String s) { if (s.length() == 0) return ""; boolean [][] dp = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) dp[i][i] = true; // one char is a palindrome int max = 1; String r = new String() + s.charAt(0); for (int i = s.length() -2; i >= 0; i--) { for (int j = i+1; j < s.length(); j++) { if ((j-i) == 1) // if two adjacent char, just check if they are the same. dp[i][j] = s.charAt(i) == s.charAt(j); else dp[i][j] = (s.charAt(i) == s.charAt(j))? dp[i+1][j-1] : false; if (dp[i][j] && j-i+1 > max) { max = j-i+1; r = s.substring(i, j+1); } } } return r; } }

The above dp algorithm gives O(n^2) run time and O(n^2) space. But think about it, the dp is just starting from one char and extending it to both size. So we can simply scan through every char in the input string, and search to left and right for each character see if we can find a palindrome. This only takes O(1) space, and the same O(n^2) time.

You can also use the length of the string and the starting char instead of the start and end of the string, which might be more intuitive to come out

public class Solution { public String longestPalindrome(String s) { boolean [][] dp = new boolean [s.length()+1][s.length()]; //int i = 1; size of the string we are checking //int j = 0; start index of the current string int max = 1; String res = String.valueOf(s.charAt(0)); for (int i = 1; i < dp.length; i++) { for (int j = 0; j <= s.length() - i; j++) { if (i == 1) dp[i][j] = true; //one char is always palindrome else if ( i == 2) dp[i][j] = s.charAt(j) == s.charAt(j+1); else dp[i][j] = dp[i-2][j+1] && s.charAt(j) == s.charAt(j+i-1); if (dp[i][j] && i > max) { max = i; res = s.substring(j, j + i); } } } return res; } }