題目敘述

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

預設函數

int longestPalindrome(char * s){

}

題目限制

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

解題過程及程式碼

本題是Greedy的第二題，這個主題似乎都喜歡叫你找最大值，給一個由小寫或大寫字母所組成的字串，回傳由這些字母可以形成的最長迴文 (Palindrome)有多長？所謂的迴文就是由右讀到左和由左讀到右是完全相同的。

• 想法是用array記錄每個字元出現的次數，再一個一個檢查
  • A. 若某字母出現偶數次，則不論是否有一個或多個偶數都可以形成迴文
    • [例如] aa自己是迴文，bbbb出現偶數次搭配a或aa，則bbabb或bbaabb都可以配合形成迴文。
    • [計算] 如果出現偶數次就可以讓迴文長度增加出現次數。
  • B .若出現的是奇數次，則分成兩種情況：
    • 1. 只有1個字母是奇數次，其他都是偶數次，則a自身是迴文，bbb也是迴文，計算時迴文長度增加出現次數。
    • 2. 若出現多個奇數次，則除了第一次外每次會增加[出現次數 - 1]的迴文長度。
      • [例如] aaabbb，最長迴文就是baaab或abbba，長度都是5(第1個奇數增加3 + 第2個奇數增加3 - 1)。
      • [例如] aaabbbbb，最長迴文就是abbbbba或bbaaabb，長度都是7(第1個奇數增加3 + 第2個奇數增加5 - 1)。
• 程式碼上傳

  int longestPalindrome(char * s){
      int char_array[128] = {0};
      int i;
      int only_one_char_flag = 0, odd_number_char_flag = 0, ret = 0;
  
      i = 0;
      while (s[i] != '\0') {
          char_array[s[i]] += 1;
          i++;
      }
  
      for (i=0; i<128; i++) {
          if (char_array[i] == 0) {
              continue;
          }
  
          if ((odd_number_char_flag == 0) && ((char_array[i] % 2) == 1)) {  // 判斷是不是第一次出現奇數次
              ret += char_array[i];
              odd_number_char_flag = 1;
          } else if ((char_array[i] % 2) == 1) {  // 判斷是奇數次
              ret += char_array[i] - 1;
          } else if ((char_array[i] % 2) == 0) {  // 判斷是偶數次
              ret += char_array[i];
          }
      }
      return ret;
  }