#409. Longest Palindrome

題目描述

給你一個包含小寫和大寫字母的字串s，回傳這些字母所能組成的最長的回文。

同一個字母的大小寫不能視作同一個字母，舉例來說"Aa"不能算是回文。

限制條件

1 <= s.length <= 2000
字串s只包含大小寫的字母。

解題思路

回文就是由前往後讀和由後往前讀都是一樣的字母排序，像是"aabbaa"、"abcba"。所以可以成立回文的字母數量結構有兩種，「全部都是偶數」和「一個奇數其他都是偶數」。所以接下來我們只要計算字母的數量，偶數的字母全部都能組成回文，如果有一個奇數的字母，也可以把它算在回文裡面，但是如果有兩個以上的奇數字母，只能挑一個加入回文。另外如果奇數字母大於2以上，它的偶數的部分也可以被用來組成回文，因此我們會把它減去1之後的長度也算在回文長度上。

Hash Table

public class Solution {
	public int LongestPalindrome(string s) {
        var ht = new Hashtable();
        foreach(var i in s){
          if(ht.Contains(i)) ht[i] = (int)ht[i]+1;
          else ht.Add(i,1);
        }
        int odd = 0;
        int len = 0;
        foreach(DictionaryEntry i in ht){
            if((int)i.Value%2==0) len+=(int)i.Value;
            else {
              len+=(int)i.Value-1;
              odd = 1;
            }
        }
        return len+odd;
    }    
}

複雜度分析：

時間複雜度：HashTable最多只會有52個大小寫字母，而計算所有字母則需要花上s.length的時間，最差的情況會花上(n+52)的時間，所以時間複雜度為O(n)。
空間複雜度：HashTable最多只會有52個大小寫字母，所以空間最多使用O(52)，可以把空間複雜度視為O(1)。

學習重點

Hashtable