题解 | 包含所有三种字符的子字符串数目
题干分析:
题目意思直接明了,即计数一个只包含小写字母a,b,c的字符串种找到有多少包含a,b,c三种字符的子串.
算法思路:
不难意识到,任何包含包含a,b,c三个字符的子串的子串都是符合题目要求的子串,人话就是在最小的包含a,b,c三个字符的字串基础上拼接所有其他字符或字符串均符合题意.由此我们使用双指针并从头(left = right = 0)开始寻找,到第一个符合要求的字串,之后符合要求的字串数目就是n(字符串总长)-left,找下一类型的字串时移动right即可继续寻找操作.
实现代码:
int numberOfSubstrings(string s) {
int n = static_cast<int>(s.size());
unsigned A = 0, B = 0, C = 0;
int left = 0, right = 0;
int ans = 0;
while (right <= n) {
if (A && B && C) {
ans += n - right + 1;
if (s[left] == 'a') --A;
else if (s[left] == 'b') --B;
else --C;
++left;
continue;
}
if (right != n) {
if (s[right] == 'a') ++A;
else if (s[right] == 'b') ++B;
else ++C;
}
++right;
}
return ans;
}
复杂度分析:
- 时间复杂度: 每个字符最多进出一次计数范围,因此总时间复杂度为O(n).
- 空间复杂度: 只使用到了常数的额外空间,因此总空间复杂度为O(1).
