public String longestPalindrome(String s){ if (s == null || s.length() == 0) { return""; } int n = s.length(); String maxStr = ""; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { if (isValid(s, i, j) == true) { if (j - i + 1 > maxStr.length()) { // update maxStr maxStr = s.substring(i, j + 1); } } } } return maxStr; }

privatebooleanisValid(String s, int lo, int hi){ int n = hi - lo + 1; for (int i = 0; i < n / 2; ++i) { if (s.charAt(lo + i) != s.charAt(hi - i)) { returnfalse; } } returntrue; }

public String longestPalindrome(String s){ if (s == null || s.length() == 0) { return""; } int n = s.length(); StringBuilder longest = new StringBuilder(); for (int i = 0; i < n; ++i) { findPalindrome(s, i, i, longest); // odd findPalindrome(s, i, i + 1, longest); // even } return longest.toString(); } privatevoidfindPalindrome(String s, int lo, int hi, StringBuilder longest){ int n = s.length(); StringBuilder sb = new StringBuilder(); while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) { if (lo == hi) { sb.append(s.charAt(lo)); } else { sb.insert(0, s.charAt(lo)); sb.append(s.charAt(hi)); } --lo; ++hi; } if (sb.length() > longest.length()) { longest.delete(0, longest.length()); longest.append(sb); } }

Time: $O(N^2)$ Space: $O(N)$

DP

Based on the brute-force solution, we can improve on it by avoiding unnecessary re-computation while validating palindromes. Consider the case ababa. If we already knew that bab is a palindrome, it is obvious that ababa must be a palindrome since the two end letters are the same.

So we can definedp[i][j] as true if the substring S(i, j) is a palindrome.

The recurrence is then obvious: dp[i][j] = (dp[i + 1][j - 1] && Si == Sj)

The base cases are: dp[i][i] = true, dp[i][i + 1] = (Si == Si+1).

Note: Determining ranges of i and j would be easy if you pick a starting point in the graph to get some intuition. For example, in this case j starts from i + 2.