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
}

大师

其实我没写昨天那题 只是之前周赛写过那题有点印象