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
}

大師

其實我沒寫昨天那題 只是之前週賽寫過那題有點印象