409最长回文串

不念不忘少年蓝@ 2023-02-26 13:25 8阅读 0赞

## 一、前言 ##

分类：Hash Table。

问题来源LeetCode 409 难度：简单。

问题链接：[https://leetcode-cn.com/problems/longest-palindrome/][https_leetcode-cn.com_problems_longest-palindrome]

## 二、题目 ##

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

**注意:** 假设字符串的长度不会超过 1010。

**示例：**

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

## 三、思路 ##

题意的关键是通过这些字母构造，也就是字母位置我们可以调整，思路就很简单了，统计各个字母出现个数，如果某个字母出现个数是偶数个符合要求，如果有某个字母出现个数奇数个则最多只允许有一个字母出现的个数是奇数个，多于的分别减去1即可。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 409_LongestPalindrome.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107370986
    * @author  : niebingyu
    * @date    : 2020/07/15
    * @title   : 409.最长回文串
    * @purpose : 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
    * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
    * 注意:假设字符串的长度不会超过 1010。
    *
    * 示例 1:
    * 输入: "abccccdd"
    * 输出: 7
    * 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
    *
    * 来源：力扣（LeetCode）
    * 难度：简单
    * 链接：https://leetcode-cn.com/problems/longest-palindrome
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_LONGESTPALINDROME namespace NAME_LONGESTPALINDROME {
    #define NAMESPACE_LONGESTPALINDROMEEND }
    NAMESPACE_LONGESTPALINDROME
    
    class Solution 
    {
    public:
        int longestPalindrome(string s) 
        {
            int h[128] = { 0 };
            for (char c:s) ++h[c];
    
            int num = 0; // 奇数个数
            for (int n: h)
            {
                if ((n&1) == 1)
                    ++num;
            }
    
            if (num <= 1) 
                return s.size();
    
            return s.size() - num + 1;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, string str, int expect)
    {
        Solution s;
        int result = s.longestPalindrome(str);
        if (expect == result)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed." << endl;
    }
    
    // 测试用例
    void Test1()
    {
        string str = "abccccdd";
        int expect = 7;
    
        test("Test1()", str, expect);
    }
    
    NAMESPACE_LONGESTPALINDROMEEND
    // 测试 用例 END
    //
    
    void LongestPalindrome_Test()
    {
        NAME_LONGESTPALINDROME::Test1();
    }

**执行结果：**

![20200715214213485.png][]

[https_leetcode-cn.com_problems_longest-palindrome]: https://leetcode-cn.com/problems/longest-palindrome/
[20200715214213485.png]: /images/20230209/d4f125d2d87a4530be1f957895866949.png