→ surimodo: 大師 03/12 00:47
→ Rushia: 其實我沒寫昨天那題 只是之前週賽寫過那題有點印象 03/12 01:15
1358. Number of Substrings Containing All Three Characters
昨天那題的簡單版
應該先出這題阿
怎麼先出難的
思路:
跟昨天類似
遍歷s
每次都紀錄並更新a、b、c最後一次出現的index
然後取三者中最小的那個當作右邊界
right = min( a_idx, b_idx, c_idx )
這樣保證 s[right : i]這個子字串中a、b、c都至少出現一次
滿足條件的子字串會有 right + 1個
所以ans += right + 1
這樣就可以得到答案了
golang code :
func numberOfSubstrings(s string) int {
lastIdx, ans, n := []int{-1, -1, -1}, 0, len(s)
for i := 0; i<n; i++{
idx := int(s[i] - 'a')
lastIdx[idx] = i
right := min(lastIdx[0], lastIdx[1], lastIdx[2])
if right == -1 {
continue
}
ans += (right + 1)
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1741711216.A.2BC.html