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.

Notes:

  • Unsure why this doesnt work. The largest palindromic substring length are all the even characters + the largest character that goes directly in the center.

int longestPalindrome(string s)
{
    //cout << s.length() << endl;
    unordered_map<char, int> char_freq;
    char_freq.reserve(26 * 2); // letters + capital

    for (char c : s) {
        if (char_freq.find(c) != char_freq.end())
            char_freq[c]++;
        else char_freq.insert(make_pair(c, 1));
    }

    int max_odd_i = 0;
    int length = 0;

    for (auto i : char_freq) {
        if (i.second % 2 != 0 && i.second > max_odd_i)
            max_odd_i = i.second;

        else if (i.second % 2 == 0)
            length += i.second;
    }

    return length + max_odd_i;
}

int main()
{
    cout << longestPalindrome("civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth") << endl;
    cout << endl;

    cout << longestPalindrome("dccaccddccaccddccaccddccaccd") << endl;
    cout << endl;


}

Last updated