Leetcode每日一题 —— 1358. 包含所有三种字符的子字符串数目

写丑陋了。

class Solution {

public:

    int numberOfSubstrings(string s) {

        std::queue<int> q;

        std::array<int,3> cnt = {0,0,0};

        int res = 0;

        int n = s.size();

        auto jud = [&cnt]() -> int {

            return ((cnt[0] != 0) + (cnt[1] != 0) + (cnt[2] != 0) == 3);

        };

        int lp = 0,rp = 0;

        while(rp < n) {

            while(rp < n) {

                cnt[s[rp] - 'a']++;

                rp++;

                if(jud()) {

                    break;

                }

            }

            while(jud()) {

                res += n - rp + 1;

                cnt[s[lp] - 'a']--;

                lp++;

            }

        }

        return res;

    }

};

实际上关心的是每个位置后面最近的 a, b, c 分别在哪里出现，取三者中最大的下标，当前位置到这个下标所代表的子串肯定满足要求，其余包含此子串的也必然满足要求。

class Solution {

public:

    int numberOfSubstrings(string s) {

        // 只要 a, b, c 在一个子串中出现了，包含这个子串的所有子串都满足要求

        // 从左往右处理的话，在意的其实就是每个位置右边最近的 a, b, c 在哪

        // 先预先生成每个位置右边最近的 a, b, c 位置

        int n=s.size();

        int lasts[n][3];

        int runningLasts[3]={-1,-1,-1};

        for(int i=n-1;i>=0;i--){

            runningLasts[s[i]-'a']=i;

            lasts[i][0]=runningLasts[0];

            lasts[i][1]=runningLasts[1];

            lasts[i][2]=runningLasts[2];

        }

        // 接着从左往右扫描

        int res=0;

        for(int i=0;i<n;i++){

            // 必须至少包含 a, b, c，所以找这三个中最后出现下标最大的

            if(lasts[i][0]==-1||lasts[i][1]==-1||lasts[i][2]==-1){

                // 有一个为 -1 说明后面就没有同时有 a, b, c 的子串了

                break;

            }

            int lastIdx=max(lasts[i][0],max(lasts[i][1],lasts[i][2]));

            // 此时从 [i, lastIdx] 开始到 [i, n-1] 的子串都满足要求

            res+=n-lastIdx;

        }

        return res;

    }

};