Longest Palindrome

February 11, 2025•--

Calculate longest palindrome length using Set for character pairing

Given a string of letters, calculate the length of the longest palindrome that can be built

問題描述

給定一個包含大小寫字母的字符串 s，返回通過這些字母構造成的 最長的回文串 的長度。

在構造過程中，請注意 區分大小寫。比如 "Aa" 不能當做一個回文字符串。

範例

輸入：s = "abccccdd"
輸出：7
解釋：我們可以構造的最長的回文串是"dccaccd"，它的長度是 7。

輸入：s = "a"
輸出：1
解釋：最長回文串就是 "a"，長度為 1。

限制條件

1 <= s.length <= 2000
s 只包含小寫和/或大寫英文字母

解題思路

理解回文串特性回文串可以有多個成對的字符，以及最多一個單獨的字符作為中心

### 使用 Set 追蹤配對遇到重複字符時形成配對，單個字符等待配對

### 計算最長長度配對字符數 × 2 + (有剩餘字符 ? 1 : 0)

解決方案

typescript

/**
 * 使用 Set 來計算最長回文字串長度
 * 核心思想：
 * 1. 當遇到重複字母時，代表可以組成一對，放在回文字串的兩邊
 * 2. 最後如果還有剩餘字母，可以選一個當中心點
 *
 * 例如: "aabaa"
 * 1. 遇到第一個 'a' -> 加入 Set -> [a]
 * 2. 遇到第二個 'a' -> 找到一對! -> a[]a
 * 3. 遇到 'b' -> 加入 Set -> a[b]a
 * 4. 遇到第三個 'a' -> 加入 Set -> a[b]a[a]
 * 5. 遇到第四個 'a' -> 找到一對! -> aabaa
 */
export function longestPalindrome(s: string): number {
  // 用 Set 來追蹤未配對的字母
  const unpairedLetters = new Set<string>();
  // 記錄已配對的字母數量
  let pairedCount = 0;
 
// 遍歷每個字母尋找配對
for (const letter of s) {
// 如果找到配對的字母
if (unpairedLetters.has(letter)) {
// 計數加 2 並移除已配對的字母
pairedCount += 2;
unpairedLetters.delete(letter);
}
// 如果是新字母，加入 Set 等待配對
else {
unpairedLetters.add(letter);
}
}
 
// 如果有剩餘未配對的字母，可以選一個當中心
return pairedCount + (unpairedLetters.size > 0 ? 1 : 0);
}