Longest Palindrome（最长回文串）

题目 / Problem

中文： 给定一个仅由小写或大写英文字母组成的字符串 s，返回可以使用这些字母构造出的最长回文串的长度。

字母区分大小写。例如，"Aa" 不能被视为回文串。

English: Given a string s consisting 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.

示例 / Examples

Example 1

Input:  s = "abccccdd"
Output: 7

解释 / Explanation:
可以构造出的一个最长回文串是 "dccaccd"，长度为 7。
One longest palindrome that can be built is "dccaccd", whose length is 7.

最长回文串可能不唯一，题目只要求返回长度。
The longest palindrome may not be unique; only its length is required.

Example 2

Input:  s = "a"
Output: 1

解释 / Explanation:
可以构造出的最长回文串是 "a"，长度为 1。
The longest palindrome that can be built is "a", whose length is 1.

约束 / Constraints

1 <= s.length <= 2000
s 仅由小写和大写英文字母组成。
s consists only of lowercase and uppercase English letters.

回文串的字符规律 / Character Pattern of a Palindrome

回文串关于中心对称，因此字符的使用次数需要满足：
A palindrome is symmetric around its center, so character usage must satisfy:

每一对相同字符可以分别放在回文串的左右两侧，贡献长度 2。
Every pair of identical characters can be placed on opposite sides and contributes 2 to the length.
最多可以有一个未配对字符放在回文串中心，贡献长度 1。
At most one unpaired character may be placed at the center, contributing 1.
其他未配对字符不能使用。
All other unpaired characters must be omitted.

例如，某个字符出现 5 次，可以使用其中 4 个组成两对，并留下 1 个候选中心字符。
For example, if a character occurs 5 times, four copies form two pairs and one remains as a possible center character.

解题思路：使用集合配对 / Approach: Pair Characters with a Set

使用集合 unpaired 保存当前尚未找到配对的字符，并使用 length 记录已组成的回文长度：
Use a set named unpaired to store characters currently lacking a pair, and use length to track the palindrome length already formed:

如果当前字符不在集合中，将它加入集合，等待后续配对。
If the current character is absent from the set, add it and wait for a future match.
如果当前字符已经在集合中，说明找到了一对相同字符：从集合中删除它，并将 length 加 2。
If the character is already in the set, an identical pair has been found: remove it and add 2 to length.
遍历结束后，如果集合不为空，说明至少存在一个未配对字符，可以将其中任意一个放在中心，因此再加 1。
After traversal, if the set is non-empty, at least one unpaired character can occupy the center, so add 1.

这种做法会尽可能使用所有字符对，只在中心位置使用一个剩余字符，因此得到的长度最大。
This approach uses every possible pair and at most one remaining center character, producing the maximum length.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @return {number}
 */
function longestPalindrome(s) {
  const unpaired = new Set();
  let length = 0;

  for (const char of s) {
    if (unpaired.has(char)) {
      unpaired.delete(char);
      length += 2;
    } else {
      unpaired.add(char);
    }
  }

  if (unpaired.size > 0) {
    length++;
  }

  return length;
}

执行过程 / Walkthrough

以 s = "abccccdd" 为例：
For s = "abccccdd":

当前字符 / Character	操作 / Action	`unpaired`	已配对长度 / Paired Length
`a`	加入 / Add	`{a}`	0
`b`	加入 / Add	`{a, b}`	0
第一个 `c`	加入 / Add	`{a, b, c}`	0
第二个 `c`	配成一对 / Form a pair	`{a, b}`	2
第三个 `c`	加入 / Add	`{a, b, c}`	2
第四个 `c`	配成一对 / Form a pair	`{a, b}`	4
第一个 `d`	加入 / Add	`{a, b, d}`	4
第二个 `d`	配成一对 / Form a pair	`{a, b}`	6

遍历结束后，集合中还有 a 和 b。只能选择其中一个作为中心字符，所以最终长度为 6 + 1 = 7。
After traversal, a and b remain in the set. Only one can be used as the center, giving a final length of 6 + 1 = 7.

复杂度 / Complexity

设字符串长度为 n。
Let the string length be n.

时间复杂度：O(n)，每个字符只处理一次，集合操作平均为 O(1)。
Time: O(n), because each character is processed once and set operations are O(1) on average.
空间复杂度：O(1)，输入只包含 52 种英文字母，集合大小存在固定上限。
Space: O(1), because the input alphabet contains only 52 English letters, giving the set a fixed maximum size.

如果字符集不受限制，则空间复杂度可以写为 O(k)，其中 k 是不同字符的数量。
For an unrestricted character set, the space complexity would be O(k), where k is the number of distinct characters.

字符频率解法 / Frequency-Counting Approach

也可以先统计每个字符的出现次数。每个字符贡献最大的偶数部分；如果存在奇数频率，再添加一个中心字符。
Alternatively, count each character's frequency. Every character contributes its largest even portion, and one center character is added if any frequency is odd.

function longestPalindromeWithCounts(s) {
  const counts = new Map();

  for (const char of s) {
    counts.set(char, (counts.get(char) ?? 0) + 1);
  }

  let length = 0;
  let hasOddCount = false;

  for (const count of counts.values()) {
    length += count - (count % 2);

    if (count % 2 === 1) {
      hasOddCount = true;
    }
  }

  return length + (hasOddCount ? 1 : 0);
}

时间复杂度 / Time: O(n)
空间复杂度 / Space: O(1)，因为字符种类最多为 52。
The character set contains at most 52 distinct letters.

集合解法在遍历过程中直接完成配对，不需要第二次遍历频率表。
The set approach forms pairs during traversal and does not require a second pass over a frequency table.

易错点 / Common Pitfalls

大写字母与小写字母不同，例如 A 和 a 不能组成一对。
Uppercase and lowercase letters differ; for example, A and a cannot form a pair.
可以使用任意数量的字符对，但最多只能使用一个未配对字符作为中心。
Any number of character pairs may be used, but at most one unpaired character may occupy the center.
题目要求返回最长回文串的长度，不需要构造或返回回文串本身。
Return the length of the longest palindrome; constructing or returning the palindrome itself is unnecessary.
字符出现奇数次时，不是只能使用一个，而是可以使用最大的偶数部分，并可能额外使用一个中心字符。
For an odd frequency, use its largest even portion and possibly one additional center character.
不能将所有奇数频率都各加一个；整个回文串只有一个中心位置。
Do not add one for every odd frequency; the entire palindrome has only one center position.

Longest Palindrome