本文共 1447 字，大约阅读时间需要 4 分钟。

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

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。 注意: 假设字符串的长度不会超过 1010。 示例 1: 输入: “abccccdd” 输出: 7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。 回文字符串，从前向后遍历和从后向前遍历都是相同的 问题思考： 例如在s = "abccccddaa"中，有3个a，1个b，4个c，2个d 使用字符串s中的字符，任意组合，生成新的字符串，若生成的字符串为回文字符串，需要除了中心字符，其余字符只要头部出现，尾部就要出现 在字符串中，字符数量为偶数的字符，或为奇数的字符如何进行处理 1、在字符串中，字符数量为偶数的字符： 全部使用，头部放一个字符，尾部就对应放一个 2、在字符串中，字符数量为奇数的字符： 丢掉一个字符，剩下的字符数为偶数个，按照字符数量为偶数的字符进行处理 3、若有剩余的字符，随便选择一个字符当做中心字符 算法思路： 1、利用字符哈希方法，统计字符串中所有的字符数量 2、设置最长回文串偶数字符长度为max_length = 0; 3、设置是否有中心点标记flag = 0; 4、遍历每一个字符，字符数为count，若count为偶数，max_length+=count；若count为奇数，max_length += count - 1, flag = 1; 5、最终最长回文子串长度：max_length + flag 例如在s = "abccccddaa"中，有3个a，1个b，4个c，2个d 1、3个a，max_length += 2；flag = 1；如生成aa 2、1个b，max_length += 0；忽略b 3、4个c，max_length += 2；如生成ccaacc 4、2个d，max_length += 2；如生成dccaaccd flag = 1； 故可生成如：dccaaaccd、dccabaccd 最终长度：max_length + flag = 8 + 1 = 9 代码如下：

class Solution {
   public:    int longestPalindrome(string s) {
           int char_map[128] = {
   0};    //字符哈希        int max_length = 0;        int flag = 0;        for (int i = 0; i < s.length(); i++){
               char_map[s[i]]++;        }        for (int i = 0; i < 128; i++){
               if (char_map[i] % 2 == 0){
                   max_length += char_map[i];            }            else{
                   max_length += char_map[i] - 1;                flag = 1;            }        }        return max_length + flag;    }};

转载地址：http://pvxmb.baihongyu.com/