来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
坚持打卡的第10天!
一、题目描述
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 "Aa"
不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
- 输入:"abccccdd"
- 输出:7
- 解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是7。
二、题解
回文串的规律:从左往右数和从右往左数的相同位置上的字符是一样的。那么要想得到回文串,必须找到成对出现的字符。
因此只要从左往右遍历所有的字符,统计出每个字符出现的次数,只要字符出现的次数超过两次,它就能成为回文串中的一员。而出现次数只有一次的字符,就只能乖乖放在最中间了,并且所有只出现一次的字符中,只能选一个放到中间。
三、代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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; } }; |
评论