Thursday, October 27, 2016

LeetCode OJ - Longest Palindrome

Problem:

Please find the problem here.

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;
}

No comments :

Post a Comment