計算回文子序列數目 Unique Length 3 Palindromic Subseq_Leetcode#1930

這題的題目在這裡:Unique Length-3 Palindromic Subsequences

題目敘述

舉例，aba者種形式的序列，就是長度為3的回文序列。

測試範例

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

約束條件

Constraints:

• 3 <= s.length <= 10^5
• s consists of only lowercase English letters.

演算法

題目已經明確說字串s都是由英文小寫字母所組成。

此外，長度為三的回文子序列可寫成如下形式:

長度為三的回文子序列 = 邊界字元 + 中心字元 + 邊界字元

因此，我們可以先從邊界字元著手，找出對應左邊界和右邊界。

接著，再計算出中心自元有幾種可能(=夾在內部的子字串有幾個不同的字元)

最後，累加方法數的總和，就是長度為三的回文子序列的數目。

程式碼

class Solution:
　def countPalindromicSubsequence(self, s):
　　
　　# counting of length 3 palindrome
　　counting = 0

　　# Scan from a to z as boundary character
　　for boundary in string.ascii_lowercase:
　　　
　　　# leftmost position of boundary character
　　　# rightmost position of boundary character
　　　left, right = s.find(boundary), s.rfind(boundary)

　　　if left != -1:

　　　　# candidates of center character
　　　　unique_chars = set( s[left+1:right])
　　　　counting += len( unique_chars )

　　return counting

複雜度分析

時間複雜度: O(26n) = O(n)

​外層迴圈，考慮每個英文字母最為邊界字元O(26)

內層陣列分割和集合建造，找出每個中心字元，耗費O(n)

空間複雜度: O(n)

陣列分割和集合建造都會付出O(n)的空間成本

關鍵知識點

長度為三的回文子序列 = 邊界字元 + 中心字元 + 邊界字元

因此，我們可以先從邊界字元著手，找出對應左邊界和右邊界。

接著，再計算出中心自元有幾種可能(=夾在內部的子字串有幾個不同的字元)

最後，累加方法數的總和，就是長度為三的回文子序列的數目。

Reference:

[1] Python O(26n) by boundary linear scan [w/ Comment] - Unique Length-3 Palindromic Subsequences - LeetCode