leetcode-最长回文串

409. 最长回文串

题解：

1. 统计每个字符出现的次数。
2. 回文字符串的特点是，除了最中间的一个字符可以出现一次外，其他字符都应该成对出现（即出现次数为偶数）来保持对称。
3. 遍历字符出现的次数，将偶数次全部计入最长回文串的构造中。对于奇数次出现的字符，将其次数减一变成偶数后加入到回文串中，如果回文串中还没有中心字符，可以把其中一个奇数次字符整体加入到回文串中作为中心。

class Solution:
    def longestPalindrome(self, s: str) -> int:
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1
        # 初始化回文串的长度为0
        length = 0

        # 标记是否已加入中心字符
        center_added = False
        for count in char_count.values():
            if count % 2 == 0:
                length += count
            else:
                # 如果出现奇数次，并且还没有中心字符，
                # 可以选择一个作为中心，因此总长度+1
                # 同时将剩余的偶数部分加入长度
                if not center_added:
                    length += 1
                    center_added = True
                length += count - 1
        return length

原文地址：https://blog.csdn.net/weixin_33631777/article/details/136362165

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！