package question;

import java.util.concurrent.Callable;
import java.util.concurrent.ThreadPoolExecutor;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question5 {

 // if (i==j) true
 // if (i+1==j && s[i]==s[j])
 // if (s[i]==s[j] && dp[i+1][j-1])
 public String longestPalindrome(String s) {
 int n = s.length();
 char[] c = s.toCharArray();
 boolean[][] dp = new boolean[n][n];
 for (int i = 0; i < n; i++) {
 dp[i][i] = true;
 }
 for (int k = 1; k < n; k++) {
 for (int i = 0; i < n - k; i++) {
 int j = i + k;
 if (c[i] == c[j] && (k == 1 || dp[i + 1][j - 1]))
 dp[i][j] = true;
 }
 }
 for (int k = n - 1; k > 0; k--) {
 for (int i = 0; i < n - k; i++) {
 int j = i + k;
 if (dp[i][j]) return s.substring(i, j);
 }
 }
 return s.substring(0, 1);
 }
}