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

閱讀時間約 4 分鐘
raw-image

這題的題目在這裡: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:

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

85會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目會給我們一個routes 陣列,裡面都是分別代表每一條公車路線所對應的公車站編號。 題目要求我們計算出,從起點站source到終點站target的最精簡公車路線搭乘次數是幾次? 也就是說,就是在最少轉乘的前提下,旅途中需要搭乘幾條公車路線?
題目會給我們一個pair陣列,裡面都是原本陣列相鄰元素形成的pair,順序已經被打散。 要求我們從pair陣列重建出原本的陣列。 答案可能有不只一組,任選一組回傳即可。
題目會給定我們一個字串s,要求我們計算出同質子字串有幾個? 同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。
題目會給定我們兩個點座標,分別是起點和終點。 另外,還有一個參數t,代表時間限制。 從起點出發之後,每一秒鐘,我們必須選擇一個N8 8連通的方向,往鄰居的格子點移動。(題目有特別強調,每一秒必須強制移動到下一個格子點,不能停留在原地) 請問我們能不能在時間限制內,從起點走到終點?
題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 題目給我們一次做多的機會,也就是A交易日買進,B交易日賣出,請問最大獲利是多少?(此處不需要考慮現實面的交易稅、手續費...等因素) 如果無法獲利,則題目要求return 0。
場景是防禦城市,免於怪獸的入侵 題目會給定兩個陣列 一個是dist,代表怪獸和城市之間的距離 一個是speed,代表怪獸每分鐘前進的距離,也就是怪獸的速度 有一把一開始已經充滿電的電動槍,一槍可以擊殺一隻怪獸,擊發後需要耗費一分鐘的冷卻時間讓電動槍再次充滿電。 題目要求我們計算最多可以消滅幾隻怪獸?
題目會給我們一個routes 陣列,裡面都是分別代表每一條公車路線所對應的公車站編號。 題目要求我們計算出,從起點站source到終點站target的最精簡公車路線搭乘次數是幾次? 也就是說,就是在最少轉乘的前提下,旅途中需要搭乘幾條公車路線?
題目會給我們一個pair陣列,裡面都是原本陣列相鄰元素形成的pair,順序已經被打散。 要求我們從pair陣列重建出原本的陣列。 答案可能有不只一組,任選一組回傳即可。
題目會給定我們一個字串s,要求我們計算出同質子字串有幾個? 同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。
題目會給定我們兩個點座標,分別是起點和終點。 另外,還有一個參數t,代表時間限制。 從起點出發之後,每一秒鐘,我們必須選擇一個N8 8連通的方向,往鄰居的格子點移動。(題目有特別強調,每一秒必須強制移動到下一個格子點,不能停留在原地) 請問我們能不能在時間限制內,從起點走到終點?
題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 題目給我們一次做多的機會,也就是A交易日買進,B交易日賣出,請問最大獲利是多少?(此處不需要考慮現實面的交易稅、手續費...等因素) 如果無法獲利,則題目要求return 0。
場景是防禦城市,免於怪獸的入侵 題目會給定兩個陣列 一個是dist,代表怪獸和城市之間的距離 一個是speed,代表怪獸每分鐘前進的距離,也就是怪獸的速度 有一把一開始已經充滿電的電動槍,一槍可以擊殺一隻怪獸,擊發後需要耗費一分鐘的冷卻時間讓電動槍再次充滿電。 題目要求我們計算最多可以消滅幾隻怪獸?
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
  在 CPU 中,存在多種不同的資料風險(Hazard),這些風險可能會影響指令的執行順序或導致指令的停滯。 常見的Hazard種類有: 結構風險(Structural Hazards):當多個指令同時要求同一個硬體結構時,可能會發生結構風險,總之意思就是硬體資源不夠。例如,當一個指令正在寫入記憶
Thumbnail
不論是行政人員,會計、人資、管理,幾乎都會碰到人員年資的計算,每次要計算年資有沒有覺得頭很痛,怎麼算怎麼錯呢?其實只要EXCEL的一個函數馬上解決!! TIPS: DATEDIF(起始日期,結束日期,單位) TODAY():今天日期 Y:開始日到結束日已滿的年數 YM:開始日到結束日,忽略整數年後的
計算免疫学 市場の現状と将来展望に関する包括的な洞察を提供する、車速センサー市場2023年調査報告書がリリースされました。当レポートでは、業界の市場動向、成長促進要因、課題、機会などの詳細な分析に加え、競争環境と市場主要企業の市場シェア分析についても徹底検証しています。https://issuu
路線最近未必最快 更無關好玩與否 準時真的比遲到好嗎 學歷好、收入佳無關乎幸福 地磚聲響特別清脆 路面硬度與平整如何取捨 紅綠燈數量也得考量 若讀書痛苦、工作乏味就算了 錯過夕陽還有餘暉裡北斗七星
Thumbnail
這篇文章主要介紹 TCP 可靠性傳輸服務、連接管理、流量控制及擁塞控制等...
Thumbnail
一天24小時,想你的次數應該有近百次。 從那一天後,算一算也21天左右了,至今遺憾依舊滿檔,甚至會想到說哪一天如果我突然有什麼樣的意外,誰來守護你,你這輩子是否會記得我曾經這麼深深的喜歡你、在意你。 假使,老天爺讓我苟活30年,那我可不可以奢求最後的幾年能有你的陪伴。 其實我不知道,因為現在看來這
Thumbnail
這篇主要是討論一下投資組合報酬率計算方式,透過五個簡單的步驟計算出,屬於自己年度年報酬率。另外也分享一下常見計算投資報酬率的難處有哪些,相信看完的朋友也可以動手計算一下自己的投資報酬。 文中附上試算表,讓大家可以好好計算。 上圖是一個簡單的例子,為了看了避免數字看表太燒腦,用文字描述的說明一下。
計算機概論這門課是大學一年級選修中的必修課。授課老師只有一人,包辦了整個學期的課程,內容具體教了甚麼,在學生時代就沒理解過,總結個人求學生涯,算是很失敗的一門課之一。 三十多年前,彼時電腦不普及,要使用得去學校的資訊中心。困難的求學方式及非醫學院必備智能,使個人學習心態傾向不積極。老師教學時也慵懶,
Thumbnail
狗貓預產期的計算方式百百種,一次替大家一網打盡。下次遇到要產檢的狗貓時可以驗證看看準不準!
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
  在 CPU 中,存在多種不同的資料風險(Hazard),這些風險可能會影響指令的執行順序或導致指令的停滯。 常見的Hazard種類有: 結構風險(Structural Hazards):當多個指令同時要求同一個硬體結構時,可能會發生結構風險,總之意思就是硬體資源不夠。例如,當一個指令正在寫入記憶
Thumbnail
不論是行政人員,會計、人資、管理,幾乎都會碰到人員年資的計算,每次要計算年資有沒有覺得頭很痛,怎麼算怎麼錯呢?其實只要EXCEL的一個函數馬上解決!! TIPS: DATEDIF(起始日期,結束日期,單位) TODAY():今天日期 Y:開始日到結束日已滿的年數 YM:開始日到結束日,忽略整數年後的
計算免疫学 市場の現状と将来展望に関する包括的な洞察を提供する、車速センサー市場2023年調査報告書がリリースされました。当レポートでは、業界の市場動向、成長促進要因、課題、機会などの詳細な分析に加え、競争環境と市場主要企業の市場シェア分析についても徹底検証しています。https://issuu
路線最近未必最快 更無關好玩與否 準時真的比遲到好嗎 學歷好、收入佳無關乎幸福 地磚聲響特別清脆 路面硬度與平整如何取捨 紅綠燈數量也得考量 若讀書痛苦、工作乏味就算了 錯過夕陽還有餘暉裡北斗七星
Thumbnail
這篇文章主要介紹 TCP 可靠性傳輸服務、連接管理、流量控制及擁塞控制等...
Thumbnail
一天24小時,想你的次數應該有近百次。 從那一天後,算一算也21天左右了,至今遺憾依舊滿檔,甚至會想到說哪一天如果我突然有什麼樣的意外,誰來守護你,你這輩子是否會記得我曾經這麼深深的喜歡你、在意你。 假使,老天爺讓我苟活30年,那我可不可以奢求最後的幾年能有你的陪伴。 其實我不知道,因為現在看來這
Thumbnail
這篇主要是討論一下投資組合報酬率計算方式,透過五個簡單的步驟計算出,屬於自己年度年報酬率。另外也分享一下常見計算投資報酬率的難處有哪些,相信看完的朋友也可以動手計算一下自己的投資報酬。 文中附上試算表,讓大家可以好好計算。 上圖是一個簡單的例子,為了看了避免數字看表太燒腦,用文字描述的說明一下。
計算機概論這門課是大學一年級選修中的必修課。授課老師只有一人,包辦了整個學期的課程,內容具體教了甚麼,在學生時代就沒理解過,總結個人求學生涯,算是很失敗的一門課之一。 三十多年前,彼時電腦不普及,要使用得去學校的資訊中心。困難的求學方式及非醫學院必備智能,使個人學習心態傾向不積極。老師教學時也慵懶,
Thumbnail
狗貓預產期的計算方式百百種,一次替大家一網打盡。下次遇到要產檢的狗貓時可以驗證看看準不準!