Longest Palindrome

给出一堆字符,看看他们能组成的最长palindrome string是多长

Solution

hash表:偶数次的字符,次数加到SUM;奇数次的字符,次数-1加到SUM;

SUM == 字符窜总长度,直接返回,否则+1返回;

code

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int longestpalindrom(const string& str)
{

    map<char, int> hash;
    for(int i = 0; i<(int)str.length(); i++)
    {
        hash[str[i]]++;
    }

    int sum = 0;
    for(map<char, int>::iterator it = hash.begin(); it != hash.end(); it++)
    {
        if(it->second < 2)
        {
            continue;   
        }

        if(it->second%2 == 0)
        {
            sum += it->second;   
        }
        else
        {
            sum += it->second/2;
        }
    }

    if(sum == (int)str.length())
    {
        return sum;   
    }
    else
    {  
        return sum+1; 
    }

    return 0;

}

int main()
{
    string str = "aaaabbbbccee";
    cout<<longestpalindrom(str)<<endl;
    return 1;
}

results matching ""

    No results matching ""