有幾個同質子字串? Count Num of Homogenous Substrings Leetcode #1759

閱讀時間約 4 分鐘
raw-image

這題的題目在這裡:Count Number of Homogenous Substrings

題目敘述

題目會給定我們一個字串s,要求我們計算出同質子字串有幾個?

同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。

最後,題目要求回傳答案前,必須對10^9+7做除法,取餘數當作最終答案。


測試範例

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a" appears 3 times.
"aa" appears 1 time.
"b" appears 2 times.
"bb" appears 1 time.
"c" appears 3 times.
"cc" appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

Input: s = "zzzzz"
Output: 15

約束條件

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase letters.

演算法

其實由左到右的線性掃描就可以滿足需求

每次迭代,觀察以s[i]為結尾的同質子字串有幾個。


以範例"abbcccaa"為例子

a 貢獻一組a

b 貢獻一組b

下一個 b 貢獻兩組b, bb

c 貢獻一組c

下一個 c 貢獻兩組c, cc

再下一個c 貢獻三組c, cc, ccc

a 貢獻一組a

下一個 a 貢獻兩組a, aa

總共有 1 + 1 + 2 + 1 + 2 + 3 + 1 + 2 = 13 組同質子字串。


每次迭代檢查當下這個字元有沒有和前一個字元重複

如果有重複,把重複長度+1

如果沒有重複,把重複長度reset 成1,代表這回合遇到的是新的字元。

每次迭代,把當前貢獻的同質子字串數目累加到result。


最後,result 對 10^9 + 7 做除法 取餘數,回傳最終答案即可。


程式碼

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

  result, count = 0, 0

  for i, char in enumerate(s):
   if i == 0 or s[i-1] == char:
    # update homogenous substring count, ending at s[i]
    count += 1
   else:
    # we meet a new character, different to previous one
    count = 1
   
   # accumulate total count of homogenous substring
   result += count

  return result % (10**9 + 7)

複雜度分析

時間複雜度:

O(n) 使用一次線性掃描,長度和原本的輸入字串一樣長O(n)。

空間複雜度:

O(1) 使用到的都是固定尺寸的臨時變數,為常數級別。


關鍵知識點

每次迭代,觀察以s[i]為結尾的同質子字串有幾個。


Reference:

[1] Count Number of Homogenous Substrings - LeetCode

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給定我們兩個點座標,分別是起點和終點。 另外,還有一個參數t,代表時間限制。 從起點出發之後,每一秒鐘,我們必須選擇一個N8 8連通的方向,往鄰居的格子點移動。(題目有特別強調,每一秒必須強制移動到下一個格子點,不能停留在原地) 請問我們能不能在時間限制內,從起點走到終點?
題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 題目給我們一次做多的機會,也就是A交易日買進,B交易日賣出,請問最大獲利是多少?(此處不需要考慮現實面的交易稅、手續費...等因素) 如果無法獲利,則題目要求return 0。
場景是防禦城市,免於怪獸的入侵 題目會給定兩個陣列 一個是dist,代表怪獸和城市之間的距離 一個是speed,代表怪獸每分鐘前進的距離,也就是怪獸的速度 有一把一開始已經充滿電的電動槍,一槍可以擊殺一隻怪獸,擊發後需要耗費一分鐘的冷卻時間讓電動槍再次充滿電。 題目要求我們計算最多可以消滅幾隻怪獸?
題目會定義一組類別和介面,要求我們實做餐廳訂位報號系統。 SeatManager(int n) : 初始化餐廳最多有n個座位,n 最少是1 int reserve() : 要求返回最小的可讓客人入座的空座位編號。 void unreserve(int seatNumber) : 取消訂位,這個座位歸
題目會給們一個陣列,還有一個k值。 好陣列定義是: 有包含nums[k]的子陣列。 分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 其中, i, j 分別是子陣列的左端點和右端點 請問,好的子陣列的最大分數是多少?
題目會給們一個陣列,還有一個k值。 接著進行比大小的遊戲,規則如下: 每次取陣列前兩個元素值比大小,比較小的會被重新安排到陣列最後方,陣列前兩個元素值比大小,同樣的,比較小的會被重新安排到陣列最後方。依此類推,反覆進行比大小的遊戲。 請問第一個能連贏k回合的是哪個數字?
題目會給定我們兩個點座標,分別是起點和終點。 另外,還有一個參數t,代表時間限制。 從起點出發之後,每一秒鐘,我們必須選擇一個N8 8連通的方向,往鄰居的格子點移動。(題目有特別強調,每一秒必須強制移動到下一個格子點,不能停留在原地) 請問我們能不能在時間限制內,從起點走到終點?
題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 題目給我們一次做多的機會,也就是A交易日買進,B交易日賣出,請問最大獲利是多少?(此處不需要考慮現實面的交易稅、手續費...等因素) 如果無法獲利,則題目要求return 0。
場景是防禦城市,免於怪獸的入侵 題目會給定兩個陣列 一個是dist,代表怪獸和城市之間的距離 一個是speed,代表怪獸每分鐘前進的距離,也就是怪獸的速度 有一把一開始已經充滿電的電動槍,一槍可以擊殺一隻怪獸,擊發後需要耗費一分鐘的冷卻時間讓電動槍再次充滿電。 題目要求我們計算最多可以消滅幾隻怪獸?
題目會定義一組類別和介面,要求我們實做餐廳訂位報號系統。 SeatManager(int n) : 初始化餐廳最多有n個座位,n 最少是1 int reserve() : 要求返回最小的可讓客人入座的空座位編號。 void unreserve(int seatNumber) : 取消訂位,這個座位歸
題目會給們一個陣列,還有一個k值。 好陣列定義是: 有包含nums[k]的子陣列。 分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 其中, i, j 分別是子陣列的左端點和右端點 請問,好的子陣列的最大分數是多少?
題目會給們一個陣列,還有一個k值。 接著進行比大小的遊戲,規則如下: 每次取陣列前兩個元素值比大小,比較小的會被重新安排到陣列最後方,陣列前兩個元素值比大小,同樣的,比較小的會被重新安排到陣列最後方。依此類推,反覆進行比大小的遊戲。 請問第一個能連贏k回合的是哪個數字?
你可能也想看
Google News 追蹤
Thumbnail
1.0 從函數到函算語法 1.1 句子成份 九 屈折變化沒有標誌句子成份如何構成句子的規則﹗這是我們的另一個觀察。句子成份屬規範性的操作指引。現再返回《文通》的意見。《文通》將詞分成七種便是語法上的規範性指引。就句讀而言,《文通》說﹕ 「夫文者,集句以成,如錦繡然,故謂之文。欲知文,
Thumbnail
1.0 從函數到函算語法 1.1 句子成份 本書關注的是句子成份的分析。 如前述,詞類和句子成份是兩個很不一樣的概念。 詞類的劃分屬歸類性的描述。我們先有一個給定的詞彙,然後劃分若干詞類,比如名詞﹑動詞﹑形容詞等,再進而對詞彙中的每一個詞進行分類,即說某詞屬名詞﹑某詞屬動詞﹑某詞可以是名
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
接續著上次提到的 COUNT、COUNTA,我們再稍稍延伸一點,把 COUNT 函式的家族補完,介紹最後的兩名成員:COUNTUNIQUE 跟 COUNTBLANK。
Thumbnail
最近每天都有同學在解題社群提問這類型的問題,有些同學甚至po出解答來提問,表示看了解答卻還是看不懂,畢竟有時候「詳解」也沒辦法完整表達所有觀念。 排列組合是一門龐大的章節,許多人聞排組而色變,但排列組合的本質其實還是「窮舉法」,也就是把全部的可能通通列出來,只是很多地方我們可以透過計算讓窮舉變得更
Thumbnail
這是「按條件算OO」系列文的第二篇教學!今天會來聊聊 COUNTIF、COUNTIFS 和 COUNTUNIQUEIFS。
Thumbnail
1.0 從函數到函算語法 1.1 句子成份 九 屈折變化沒有標誌句子成份如何構成句子的規則﹗這是我們的另一個觀察。句子成份屬規範性的操作指引。現再返回《文通》的意見。《文通》將詞分成七種便是語法上的規範性指引。就句讀而言,《文通》說﹕ 「夫文者,集句以成,如錦繡然,故謂之文。欲知文,
Thumbnail
1.0 從函數到函算語法 1.1 句子成份 本書關注的是句子成份的分析。 如前述,詞類和句子成份是兩個很不一樣的概念。 詞類的劃分屬歸類性的描述。我們先有一個給定的詞彙,然後劃分若干詞類,比如名詞﹑動詞﹑形容詞等,再進而對詞彙中的每一個詞進行分類,即說某詞屬名詞﹑某詞屬動詞﹑某詞可以是名
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
接續著上次提到的 COUNT、COUNTA,我們再稍稍延伸一點,把 COUNT 函式的家族補完,介紹最後的兩名成員:COUNTUNIQUE 跟 COUNTBLANK。
Thumbnail
最近每天都有同學在解題社群提問這類型的問題,有些同學甚至po出解答來提問,表示看了解答卻還是看不懂,畢竟有時候「詳解」也沒辦法完整表達所有觀念。 排列組合是一門龐大的章節,許多人聞排組而色變,但排列組合的本質其實還是「窮舉法」,也就是把全部的可能通通列出來,只是很多地方我們可以透過計算讓窮舉變得更
Thumbnail
這是「按條件算OO」系列文的第二篇教學!今天會來聊聊 COUNTIF、COUNTIFS 和 COUNTUNIQUEIFS。