Back to Leetcode

Readme

Two_Pointers/1358.Number-of-Substrings-Containing-All-Three-Characters/Readme.md

latest632 B
Original Source

1358.Number-of-Substrings-Containing-All-Three-Characters

我们固定滑窗的左端点i,向右探索右端点j。当我们发现移动到某处的j,使得[i:j]恰好至少包含a,b,c各一个的时候,那么意味着右端点其实可以直至在从j到n-1的任何位置,都满足条件。这样的区间有n-j个。

此时我们查看下一个i作为左端点,同样为了满足[i:j]恰好至少包含a,b,c各一个,j必然向右移动。同理,可以计算出以i为左端点、符合条件的区间的个数。

最终答案就是以每个i作为左端点时,符合条件的右端点的数目的总和。