本篇同步發布於Blog: [解題] LeetCode - 409 Longest Palindrome

平台：

LeetCode

題號：

409 - Longest Palindrome

題目連結：

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

題目說明：

        輸入1個字串，裡面有不同的字元，且大小寫也視為不同，求從這些字元組成最大回文的長度。

比如範例輸入的abccccdd，能組成最大長度為7的回文，有可能是ccdadcc或者其他的組合。

解題方法：

分析每個字元出現的頻率，假如X字元出現偶數次，則它一定能全部拿去組回文。但如果X字元出現奇數次，則只能取它的數量-1後再拿去組回文，假如目前回文的長度是偶數，則剛剛那筆奇數次的字元，被-1的數量要再補上去，這樣仍是回文。

以範例輸入的abccccdd：

• a的出現次數為1，能組成回文，目前回文長度為1
• b的出現次數為1，無法加進回文，回文長度仍不變
• c的出現次數為4，能組成回文，目前回文長度為5
• d的出現次數為2，能組成回文，目前回文長度為7

所以最長的長度為7。

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <string>
using namespace std;
 
class Solution {
public:
    int longestPalindrome(string s) {
        int letters[128] = {0};
 
        for(char c : s){
            letters[c]++;
        }
 
        int ans = 0;
        for(int i = 0 ; i < 128;++i){
            int curLen = letters[i];
            if(letters[i] % 2 == 1){
                curLen--;
            }
 
            ans += curLen;
            if(ans % 2 == 0 && letters[i] % 2 == 1){
                ans++;
            }
        }
 
        return ans;
    }
 
};
 
int main() {
	Solution sol;
	cout << sol.longestPalindrome("abccccdd") << endl;
	return 0;
}

using System;

namespace LeetCode409
{
	public class Solution {
		public int LongestPalindrome(string s) {
			int[] letters = new int[128];
			foreach(char c in s){
				letters[(int)c]++;
			}

			int ans = 0;
			for(int i = 0 ; i < 128;++i){
				int curLen = letters[i];
				if(letters[i] % 2 == 1){
					curLen--;
				}

				ans+=curLen;
				if(ans % 2 == 0 && letters[i] % 2 == 1){
					ans++;
				}
			}
			return ans;
		}
	}
	
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.LongestPalindrome("abccccdd"));
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/400-499/409.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/400-499/409.cs