题解 | 包含所有三种字符的子字符串数目

题干分析:

题目意思直接明了,即计数一个只包含小写字母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).