LeetCode 筆記 - 1930. Unique Length-3 Palindromic Subsequences

題目在此 1930. Unique Length-3 Palindromic Subsequences

給定一個字串，請問裡面有幾個長度為 3 的迴文子序列？

解題思維

名詞解說：

• Subsequence
• Palindrome
• Manacher’s Algorithm
• Dynamic programming

這題很弔詭，看到 Subsequences 就會想到 DP，看到迴文就會想到 Manacher’s Algorithm，但是這題其實不用這麼複雜。

先分析一下題目，長度為 3 的迴文子序列，也就是說只要前後相同，中間就可以是任意字元。
題目也說了，相同組合的算一個，所以我們只要找到每個字元的第一個出現位置與最後一個出現位置，就可以知道這個字元可以組成幾個迴文子序列。

所以這題的關鍵找到每個字元的第一個出現位置與最後一個出現位置就可以了，中間就用 set 來處理重複的字元。

程式碼

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:

        if (size := len(s)) == 3:
            return 1 if s[0] == s[-1] else 0

        s_set = set(s)

        result = 0
        for c in s_set:
            between_set = set(s[s.find(c) + 1:s.rfind(c)])
            result += len(between_set)

        return result

相關文章

• LeetCode 筆記 - 1143. Longest Common Subsequence
• LeetCode 筆記 - 5. Longest Palindromic Substring
• LeetCode 筆記 - 32. Longest Valid Parentheses
• LeetCode 筆記 - 3. Longest Substring Without Repeating Characters
• LeetCode 筆記 - 1332. Remove Palindromic Subsequences