這題的題目在這裡:Unique Length-3 Palindromic Subsequences
題目會給我們一個字串s,內容都是由英文小寫字母組成,要求我們計算長度為3的回文子序列有多少個?
舉例,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: