MediumRating 1533
1930. Unique Length-3 Palindromic Subsequences
hash-tablestringbit-manipulationprefix-sum
解題說明
Unique Length-3 Palindromic Subsequences
題目描述：
給定字串 s，求其中長度為 3 的回文子序列有多少種不同的。長度為 3 的回文形式為 aba，即首尾字元相同、中間字元任意。
解題思路：
對於每種字元 a（26 種小寫字母），找到它在字串中第一次出現和最後一次出現的位置。
- 若字元
a在first和last之間出現了至少兩次（first < last），則所有出現在(first, last)開區間內的不同字元都可以作為中間字元b，構成回文aba。 - 統計
(first, last)之間有多少種不同字元即可。
遍歷 26 個字母，每個字母找首尾位置後用 HashSet 統計中間字元種類。
C++ 解法
複雜度分析
時間複雜度：O(26 × n) = O(n) — 對 26 個字母各掃描字串一次找首尾，再掃描一次統計中間字元。
空間複雜度：O(26) = O(1) — HashSet 最多存 26 個字元。
虛擬碼
1. Initialize result = 0 2. For each character c from 'a' to 'z': a. Find first and last occurrence of c in s b. If c appears fewer than 2 times, skip c. Count distinct characters in s[first+1 .. last-1] d. result += distinct count 3. Return result
其他解法
前綴集合/位元遮罩 O(n)：預計算前綴和後綴的字元集合（用 26 位 bitmask）。對每個位置 i，左邊出現的字元集合 ∩ 右邊出現的字元集合 就是能以 s[i] 為中心構成回文的首尾字元。用 popcount 計數。避免重複掃描，但邏輯較複雜。
暴力枚舉 O(n³)：三重迴圈枚舉所有長度 3 的子序列，檢查是否回文，用 HashSet 去重。n 大時不可行。
延伸思考
- 如果要求長度為 5 的回文子序列數量，如何推廣此方法？
- 如果字元集不是 26 個字母而是 Unicode，如何調整？
- 能否用此思路計算「最長回文子序列」？為什麼不行？兩者的本質差異是什麼？