LeetCode 409 Longest Palindrome

思路

统计字符出现次数，偶数的话直接加到sum里面，如果奇数的话减一后加到sum里面并且flag=1（标记）。最后sum要加上奇数标记flag(最后再加上1，因为所有的奇数频率中可以有一个放在正中间：aabbbcc，因此可以有一个奇数频率的字母不用-1, 但是flag是有用的，因为如果所有的字母出现次数都是偶数，那么就不需要-1了）。
技巧：字符哈希，int[128] charmap映射ASCII表中0～127的字符。

复杂度

时间复杂度O(n)
空间复杂度O(128) = O(1)

代码

public class Solution {
    /*** @param s: a string which consists of lowercase or uppercase letters* @return: the length of the longest palindromes that can be built*/public int longestPalindrome(String s) {
    // write your code hereif (s == null || s.length() == 0) {
    return 0;}int[] charmap = new int[128];int sum = 0, oddFlag = 0;for (int i = 0; i < s.length(); i++) {
    charmap[s.charAt(i)]++;}for (int i = 0; i < 128; i++) {
    if (charmap[i] % 2 == 0) {
    sum += charmap[i];} else {
    oddFlag = 1;sum += charmap[i] - 1;}}sum += oddFlag;return sum;}
}