1930. Unique Length 3 Palindromic Subsequences

Medium
Description

給定字串 s，回傳長度為 3 的迴文子序列的不同數量。即使兩個子序列來自不同的索引組合，只要字元相同就視為同一個。

Example:

Input: s = “aabca” Output: 3（“aba”, “aaa”, “aca”）

Intuition#

核心思路：長度 3 的迴文形如 X_Y_X，第一個和第三個字元相同。對每個字元 c，找到其最左和最右出現位置，中間的不重複字元數就是以 c 為首尾的迴文數。

  • 只有 26 個字母，所以外層字元最多迴圈 26 次
  • 對每個字元 c，找最左索引 left 和最右索引 right
  • 計算 [left+1, right-1] 之間有多少不同字元

Approaches#

1: Brute Force（枚舉所有三元組）#

  • 概念: 三層迴圈枚舉所有長度 3 的子序列，檢查是否迴文，用 Set 去重
  • 時間複雜度: O(n^3) - TLE
  • 空間複雜度: O(n) - Set
class Solution {
    fun countPalindromicSubsequence(s: String): Int {
        val seen = HashSet<String>()
        for (i in s.indices) {
            for (j in i + 1 until s.length) {
                for (k in j + 1 until s.length) {
                    if (s[i] == s[k]) {
                        seen.add("${s[i]}${s[j]}${s[k]}")
                    }
                }
            }
        }
        return seen.size
    }
}

⭐2: 首尾字元 + 中間不同字元數#

  • 概念: 對每個字元 c（a-z），找最左和最右出現位置，統計中間不同字元數
  • 時間複雜度: O(26 * n) = O(n) - 對每個字元掃描中間區段
  • 空間複雜度: O(1) - 常數空間（26 個字元 + Set 最多 26 個元素）
class Solution {
    fun countPalindromicSubsequence(s: String): Int {
        var count = 0
        for (c in 'a'..'z') {
            val left = s.indexOf(c)
            val right = s.lastIndexOf(c)
            if (left == -1 || left >= right) continue

            val unique = HashSet<Char>()
            for (i in left + 1 until right) {
                unique.add(s[i])
            }
            count += unique.size
        }
        return count
    }
}
補充：Prefix Set 優化

預處理每個位置的前綴字元集合，可以避免重複計算。但由於外層只有 26 次，優化幅度有限。

class Solution {
    fun countPalindromicSubsequence(s: String): Int {
        // 記錄每個字元的第一次和最後一次出現
        val first = IntArray(26) { Int.MAX_VALUE }
        val last = IntArray(26) { -1 }
        for (i in s.indices) {
            val idx = s[i] - 'a'
            first[idx] = minOf(first[idx], i)
            last[idx] = i
        }

        var count = 0
        for (c in 0 until 26) {
            if (first[c] >= last[c]) continue
            val unique = HashSet<Char>()
            for (i in first[c] + 1 until last[c]) {
                unique.add(s[i])
            }
            count += unique.size
        }
        return count
    }
}

🔑 Takeaways#

  • Pattern: 利用迴文的對稱性固定外層字元，問題簡化為統計中間的不同字元
  • 關鍵技巧: 字元集大小有限（26）是關鍵突破口，讓暴力枚舉外層字元變得可行；indexOf 和 lastIndexOf 找首尾出現位置是常用技巧