来源:力扣(LeetCode)

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

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

坚持打卡的第10天!

一、题目描述

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

在构造过程中,请注意区分大小写。比如 "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;
    }
};

最后修改:2020 年 03 月 19 日
喜欢就给我点赞吧