Leetcode-409Longest Palindrome

409. 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.

题解：

输入一个字符串，求用这个字符中的字符所能组成的最长的回文字符串的长度；
例如对于字符串：str = "abcddbcaa"：
其中一个由字符串中字符所组成的最长回文字符串为："abcdadcba"
输出该回文串长度：9
我们考虑用哈希表将字符串中每个字符出现的次数存储起来，即：
str['a'] = 3；str['b'] = 2；str['c'] = 2；str['d'] = 2；
下面来分析下：

1. 当字符出现次数 count 为偶数时：
   一定可以组成回文串，所以回文串长度 result + count；
2. 当字符出现次数 count 为奇数时：
   偶数一定可以组成回文串，所以回文串长度 result + count - 1；而多出来的那个字符可以作为回文串的中心字符；所以我们用 odd = 1 来表示存在奇数个字符；这样，只需要在输出的时候，返回 result + odd，就可以得到最长回文串的长度了；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <string>
#include <map>

using namespace std;

class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> hash_map;
        for (int i = 0; i < s.length(); i++) {
            if (hash_map.find(s[i]) == hash_map.end()) {
                hash_map.insert(map<char, int>::value_type(s[i], 1));
            }
            else {
                hash_map[s[i]] += 1;
            }
        }
        map<char, int>::iterator it;
        int result = 0;
        int odd = 0;
        for (it = hash_map.begin(); it != hash_map.end(); it++) {
            if (it->second % 2 == 0) {
                result += it->second;
            }
            else {
                odd = 1;
                result += it->second - 1;
            }
        }
        return result + odd;
    }
};

int main() {
    string str = "abcddbcaa";
    Solution s;
    printf("%d ", s.longestPalindrome(str));
    return 0;
}

结果

9

My Solution 1 (Python)

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        dict, sum, mark = {}, 0, 0
        for i in s:
            if i in dict.keys():
                dict[i] += 1
            else:
                dict[i] = 1
        for val in dict.values():
            if val % 2 == 0:
                sum += val
            else:
                sum += val - 1
                mark = 1
        return sum + mark
                

My Solution 2 (Python)

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        sum, mark = 0, 0
        char_map = [0 for i in range(128)]
        for i in range(len(s)):
            char_map[ord(s[i])] += 1
        for i in range(128):
            if char_map[i] != 0:
                if char_map[i] % 2 == 1:
                    sum += char_map[i] - 1
                    mark = 1
                else:
                    sum += char_map[i]
        return sum + mark

Reference:

def longestPalindrome(self, s):
    odds = sum(v & 1 for v in collections.Counter(s).values())
    return len(s) - odds + bool(odds)