[LeetCode] 409. Longest Palindrome

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.

Example 1:
Input: s = “abccccdd”
Output: 7
Explanation: One longest palindrome that can be built is “dccaccd”, whose length is 7.

Example 2:
Input: s = “a”
Output: 1
Explanation: The longest palindrome that can be built is “a”, whose length is 1.

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

最长回文串。

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。

在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

思路

遍历 input，并用一个 hashmap 存字母的出现次数。如果某字母已经存在于 hashmap减去它在 hashmap 内的出现次数，res += 2，这里的意思是找到了一对字母可以用于回文串；如果某字母不存在于 hashmap 则把它加入 hashmap，map[char]++。最后遍历 hashmap，看是否还存在某个字母的出现次数不为零的情况，若还有不为零的字母则最长的回文串长度是 res + 1（会形成类似aba这样的回文）；否则则是res（会形成类似abba这样的回文）。

复杂度

时间O(n)
空间O(256) - O(1)

代码

Java实现

class Solution {
    public int longestPalindrome(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return 0;
        }

        // normal case
        int res = 0;
        char[] count = new char[256];
        for (char c : s.toCharArray()) {
            if (count[c] > 0) {
                count[c]--;
                res += 2;
            } else {
                count[c]++;
            }
        }

        for (int i = 0; i < 256; i++) {
            if (count[i] != 0) {
                res++;
                break;
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
    // corner case
    if (s == null || s.length == 0) {
        return 0;
    }

    // normal case
    let map = {};
    let res = 0;
    let flag = false;
    for (let c of s) {
        if (map[c] !== undefined) {
            map[c] = undefined;
            res++;
        } else {
            map[c] = 1;
        }
    }

    for (key in map) {
        if (map[key] !== undefined) {
            flag = true;
        }
    }
    if (flag) return res * 2 + 1;
    return res * 2;
};