409.Longest Palindrome

Tags: Easy Hash Table String

Links: https://leetcode.com/problems/longest-palindrome/

---

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note: Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

---

class Solution {
public:
    int longestPalindrome(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<int> lower(26, 0), upper(26, 0);
        for (auto e : s) {
            if ('a' <= e && e <= 'z') ++lower[e - 'a'];
            else ++upper[e - 'A'];
        }

        int res = 0;
        int pos1 = -1, pos2 = -1;
        int left = count(lower, pos1);
        int right = count(upper, pos2);
        res += max(left, right);
        if (left >= right && pos1 != -1) lower[pos1] = 0;
        else if (right > left && pos2 != -1) upper[pos2] = 0;

        calculate(res, lower);
        calculate(res, upper);

        return res;
    }

    int count(const vector<int> & num, int & position)
    {
        int tmpMax = 0;
        for (int i = 0; i < 26; ++i) {
            if (num[i] & 1) {
                tmpMax = num[i];
                position = i;
            } 
        }
        return tmpMax;
    }

    void calculate(int & res, const vector<int> & num)
    {
        for (int i = 0; i < 26; ++i) {
            res += (num[i] / 2) * 2;
        }
    }
};

考虑到只有小写字母和大写字母，所以准备两个26长度的数组来代替哈希表。

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Palindrome.
Memory Usage: 8.2 MB, less than 100.00% of C++ online submissions for Longest Palindrome.

另外这道题目可以考虑把代码缩短一点，思路就是每次统计字符串里面奇数的个数，如果存在奇数，那么就是字符串的长度减去奇数的个数然后+1。举个例子，比如字符串aabbbcccd，字符串长度是9，奇数的个数是3，那么最后的长度就是9 - 3 + 1 = 7。另外就是考虑没有奇数的情况。

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Palindrome.
Memory Usage: 8.1 MB, less than 100.00% of C++ online submissions for Longest Palindrome.