【每日打卡】 [leetcode]-409 最长回文子串

马谦马谦马谦

615
文章

17
评论

2020 年 3 月 19 日 23:24:00数据结构和算法评论204字数 466阅读 1 分 33 秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindrome

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

坚持打卡的第 10 天！

【每日打卡】[leetcode]-409最长回文子串-图片1

一、题目描述

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

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

注意:

假设字符串的长度不会超过 1010 。

示例 1：

输入："abccccdd"
输出：7
解释：我们可以构造的最长的回文串是"dccaccd", 它的长度是 7 。

二、题解

回文串的规律：从左往右数和从右往左数的相同位置上的字符是一样的。那么要想得到回文串，必须找到成对出现的字符。

因此只要从左往右遍历所有的字符，统计出每个字符出现的次数，只要字符出现的次数超过两次，它就能成为回文串中的一员。而出现次数只有一次的字符，就只能乖乖放在最中间了，并且所有只出现一次的字符中，只能选一个放到中间。

三、代码

class Solution {
public:
    int longestPalindrome(string s) {
        int stat[52] = { 0 };
        int i, idx, cnt, flag;
        // 统计所有字符串出现的次数
        for (i = 0; i < s.size(); i++) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                stat[s[i] - 'a']++;
            } else {
                stat[s[i] - 'A' + 26]++;
            }
        }

        // flag 用来标记是否存在不重复的字符，可以放在最中间
        flag = 0;
        cnt = 0;
        for (i = 0; i < 52; i++) {
            if (stat[i] >= 2)
                cnt += 2 * (stat[i] / 2);

            if (!flag && stat[i] % 2)
                flag = 1;
        }
        return cnt + flag;
    }
};