Longest Palindrome

/**
 * 使用 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);
}

import { describe, expect, it } from 'vitest';
import { longestPalindrome } from './solution';

describe('longest palindrome', () => {
  it('應該處理基本案例', () => {
    // 基本案例：有配對和中心點
    expect(longestPalindrome('abccccdd')).toBe(7); // dccaccd
    expect(longestPalindrome('aabaa')).toBe(5); // aabaa
  });

  it('應該處理只有一個字母的案例', () => {
    expect(longestPalindrome('a')).toBe(1); // a
    expect(longestPalindrome('A')).toBe(1); // A
  });

  it('應該處理大小寫混合的案例', () => {
    expect(longestPalindrome('Aa')).toBe(1); // A 或 a
    expect(longestPalindrome('AaAaAa')).toBe(5); // AaaaA 或 aAAAa
  });

  it('應該處理所有字母都可以配對的案例', () => {
    expect(longestPalindrome('aaaa')).toBe(4); // aaaa
    expect(longestPalindrome('cccc')).toBe(4); // cccc
  });

  it('應該處理空字串', () => {
    expect(longestPalindrome('')).toBe(0);
  });

  it('應該處理複雜案例', () => {
    // 多個不同的字母組合
    expect(longestPalindrome('abccccddeeffggg')).toBe(13);
    // 所有字母都不同
    expect(longestPalindrome('abcdef')).toBe(1);
  });
});

Set 配對方法

這個解法的巧妙之處在於使用 Set 來追蹤未配對的字符。

算法邏輯

1. 配對檢測

   • 如果字符已在 Set 中，表示找到配對
   • 配對計數 +2，並從 Set 中移除該字符

2. 新字符處理

   • 如果字符不在 Set 中，加入 Set 等待配對

3. 最終計算

   • 配對的字符數 × 2
   • 如果有剩餘未配對字符，可選一個作為中心 (+1)

複雜度分析

• 時間複雜度: O(n) - 遍歷字符串一次
• 空間複雜度: O(k) - k 為不同字符的數量，最多為 128 (ASCII)

演算過程示例

以 s = "abccccdd" 為例：

最終：配對數 6 + 剩餘字符 1 = 7

回文串構造示例

• 配對: cc, cc, dd (6 個字符)
• 中心: 'a' 或 'b' (1 個字符)
• 可能的回文串: "dccaccd" 或 "dccbccd"