Longest Palindrome

• Lintcode : 627 / Leetcode : 409
• Level : Easy

Problem

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.

Example
Example 1:

Input : s = "abccccdd"
Output : 7
Explanation :
One longest palindrome that can be built is "dccaccd", whose length is `7`.
Notice
Assume the length of given string will not exceed 1010.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    int longestPalindrome(string &s) {
        unordered_map<char, int> count;
        bool hasOdd = false; 
        for(auto i : s) {
            count[i]++;
        }
        int length = 0;
        for (auto it = count.begin(); it != count.end(); it++) {
            if (it -> second % 2)  {
                hasOdd = true;
                length += it -> second - 1;
            }else {
                length += it -> second;
            }
        }
        return hasOdd ? length + 1 : length;
    }
};

tags: string

​