## Thursday, October 27, 2016

### LeetCode OJ - Longest Palindrome

Problem:

Analysis:

The problem allows the letters to be reordered, making it so much easier. The basic idea is to construct the longest palindrome by putting every pair I can find to the beginning and the end of the string. After exhausting all pairs, and I still have any characters left, I can stuck that at the middle.

Solution:

In fact, all I cared is the length of the longest palindrome, so I can simply implement this by first constructing the frequency count and then compute the length by summing all the even parts and check if I have a middle character. Note the 'integer' divide by 2 and then multiply it back gives the even part of the number.

Code:

#include "stdafx.h"

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

#include "LEET_LONGEST_PALINDROME.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_LONGEST_PALINDROME
{
class Solution
{
public:
int longestPalindrome(string s)
{
int frequency[256];
for (int i = 0; i < 256; i++)
{
frequency[i] = 0;
}
for (size_t i = 0; i < s.length(); i++)
{
frequency[s[i]]++;
}
int length = 0;
bool hasOdd = false;
for (int i = 0; i < 256; i++)
{
if (!hasOdd && frequency[i] % 2 == 1)
{
hasOdd = true;
}
length += (frequency[i] / 2) * 2;
}

if (hasOdd)
{
length += 1;
}

return length;
}
};
};

using namespace _LEET_LONGEST_PALINDROME;

int LEET_LONGEST_PALINDROME()
{
Solution solution;
cout << solution.longestPalindrome("abccccdd") << endl;
return 0;
}