最长回文子串（最长回文子串）

题目描述：对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串A以及它的长度n（可给可不给），请返回最长回文子串的长度。

思路1：动态规划

public class Solution { public int getLongestPalindrome(String A, int n) { //我们从第i个字符到第j个字符来判断是否是回文串 boolean[][] dp = new boolean[n][n]; int max = 0; // 字符串首尾字母长度差 (l = j-i) for(int l = 0; l < n; l++){ // 字符串起始位置 i for(int i = 0; i < n - l; i++){ // 字符串结束位置 j int j = i + l; //如果开始位置等于结束位置 if(A.charAt(i) == A.charAt(j)){ //长度如果为0或者1，直接设为true if(l == 0 || l == 1){ dp[i][j] = true; }else{ //否则，将由其内部的长度决定是不是回文 dp[i][j] = dp[i+1][j-1]; } if(dp[i][j]){ //如果i,j确定为true，判断最大长度 max = Math.max(max, l + 1); } } } } return max; } }

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

思路2：贪心算法

public int longestPalindrome(String s) { int[] count = new int[128]; int l = s.length(); for(int i = 0; i < l; i++){ char c = s.charAt(i); count[c]++; } int ans = 0; for(int v : count){ ans += v / 2 * 2; if(v % 2 == 1 && ans % 2 == 0){ ans ++; } } return ans; }