計算回文子序列數目 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

avatar-img
88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給我們一個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
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
要計算jaarruimte,手邊需要有兩個數字,一個是年度報稅單及退休基金年度總覽 (UPO) 裡面的factor A.
學習完圍棋的基礎概念後,計算三步是棋力進步很重要的一個技能。三步是指自己的第一步、對方的下一步、跟自己的下一步,總共三步棋。無論是做題或下棋時,都需要這樣練習。隨著棋力增長,計算的深度和廣度都會慢慢增加,不過我們可以從三步棋開始練習喔!你今天計算三步了嗎?
Thumbnail
題目敘述 題目給定我們一顆二元樹的根節點,要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條? 偽回文路徑路徑 的定義: 路徑經過重新排列之後,可以形成回文Palindrome,也就是頭尾鏡像對稱。 ​ 例如: 1 -> 3 -> 3 重新排列之後,可以形成 3 -> 1 -> 3
Thumbnail
安安呐~ 今天的教學是關於玩家的登入次數統計! 讓我們直接開始吧 首先呢,讓我們來建立一個永久性變量 名字的話取什麼都可以搭 所以呢,讓我們在 Renp'py 裡添加這串代碼: default persistent.login_count = 0 default persistent.l
Thumbnail
題目會給我們一個字串s,內容都是由英文小寫字母組成,要求我們計算長度為3的回文子序列有多少個? 舉例,aba者種形式的序列,就是長度為3的回文序列。
Thumbnail
  在 CPU 中,存在多種不同的資料風險(Hazard),這些風險可能會影響指令的執行順序或導致指令的停滯。 常見的Hazard種類有: 結構風險(Structural Hazards):當多個指令同時要求同一個硬體結構時,可能會發生結構風險,總之意思就是硬體資源不夠。例如,當一個指令正在寫入記憶
Thumbnail
不論是行政人員,會計、人資、管理,幾乎都會碰到人員年資的計算,每次要計算年資有沒有覺得頭很痛,怎麼算怎麼錯呢?其實只要EXCEL的一個函數馬上解決!! TIPS: DATEDIF(起始日期,結束日期,單位) TODAY():今天日期 Y:開始日到結束日已滿的年數 YM:開始日到結束日,忽略整數年後的
計算免疫学 市場の現状と将来展望に関する包括的な洞察を提供する、車速センサー市場2023年調査報告書がリリースされました。当レポートでは、業界の市場動向、成長促進要因、課題、機会などの詳細な分析に加え、競争環境と市場主要企業の市場シェア分析についても徹底検証しています。https://issuu
路線最近未必最快 更無關好玩與否 準時真的比遲到好嗎 學歷好、收入佳無關乎幸福 地磚聲響特別清脆 路面硬度與平整如何取捨 紅綠燈數量也得考量 若讀書痛苦、工作乏味就算了 錯過夕陽還有餘暉裡北斗七星
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
要計算jaarruimte,手邊需要有兩個數字,一個是年度報稅單及退休基金年度總覽 (UPO) 裡面的factor A.
學習完圍棋的基礎概念後,計算三步是棋力進步很重要的一個技能。三步是指自己的第一步、對方的下一步、跟自己的下一步,總共三步棋。無論是做題或下棋時,都需要這樣練習。隨著棋力增長,計算的深度和廣度都會慢慢增加,不過我們可以從三步棋開始練習喔!你今天計算三步了嗎?
Thumbnail
題目敘述 題目給定我們一顆二元樹的根節點,要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條? 偽回文路徑路徑 的定義: 路徑經過重新排列之後,可以形成回文Palindrome,也就是頭尾鏡像對稱。 ​ 例如: 1 -> 3 -> 3 重新排列之後,可以形成 3 -> 1 -> 3
Thumbnail
安安呐~ 今天的教學是關於玩家的登入次數統計! 讓我們直接開始吧 首先呢,讓我們來建立一個永久性變量 名字的話取什麼都可以搭 所以呢,讓我們在 Renp'py 裡添加這串代碼: default persistent.login_count = 0 default persistent.l
Thumbnail
題目會給我們一個字串s,內容都是由英文小寫字母組成,要求我們計算長度為3的回文子序列有多少個? 舉例,aba者種形式的序列,就是長度為3的回文序列。
Thumbnail
  在 CPU 中,存在多種不同的資料風險(Hazard),這些風險可能會影響指令的執行順序或導致指令的停滯。 常見的Hazard種類有: 結構風險(Structural Hazards):當多個指令同時要求同一個硬體結構時,可能會發生結構風險,總之意思就是硬體資源不夠。例如,當一個指令正在寫入記憶
Thumbnail
不論是行政人員,會計、人資、管理,幾乎都會碰到人員年資的計算,每次要計算年資有沒有覺得頭很痛,怎麼算怎麼錯呢?其實只要EXCEL的一個函數馬上解決!! TIPS: DATEDIF(起始日期,結束日期,單位) TODAY():今天日期 Y:開始日到結束日已滿的年數 YM:開始日到結束日,忽略整數年後的
計算免疫学 市場の現状と将来展望に関する包括的な洞察を提供する、車速センサー市場2023年調査報告書がリリースされました。当レポートでは、業界の市場動向、成長促進要因、課題、機会などの詳細な分析に加え、競争環境と市場主要企業の市場シェア分析についても徹底検証しています。https://issuu
路線最近未必最快 更無關好玩與否 準時真的比遲到好嗎 學歷好、收入佳無關乎幸福 地磚聲響特別清脆 路面硬度與平整如何取捨 紅綠燈數量也得考量 若讀書痛苦、工作乏味就算了 錯過夕陽還有餘暉裡北斗七星