力扣2891每日一题题解

题目：

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

题解思路

对于小白来讲，看到题目没思路咋办？管他什么算法，先暴力模拟再说~

首先根据题意，要求的字符串其实是满足这几个条件的：

        （1）只包含一个字母

        （2）连续子序列
      

首先看到子序列，那我们就直接遍历所有子序列就好了，用一个哈希表存储每一个字符串出现的次数，超过了两次了我们就直接将这个字符串长度和之前存储的结果的值进行比较，大一点的话就更新结果就好啦~

暴力代码如下：

class Solution {
    unordered_map<string, int> mp;
public:
    int maximumLength(string s) {
        int ans = -1, n = s.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; j++) {
                int flag = 0;
                for (int k = i; k <= j; k++) {
                    if (s[k] != s[i]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 1) break;
                mp[s.substr(i, j - i + 1)] += 1;
                if (mp[s.substr(i, j - i + 1)] < 3) continue;
                if (ans < j - i + 1) ans = j - i + 1;
            }
        }
        return ans;
    }
};

直接三重循环暴力就完事了，反正最多长度为50，50 * 50 * 50也才125000，肯定不会超时滴~

         但是问题来了，第二关咋办，第二等级数据量直接飙升到了500000，这样的话最多只能允许O(N + N * logN)的时间复杂度，这样的话双重循环也过不去，这样我们就得重新思考这些问题了

首先我们得仔细阅读题目意思，利用条件：

        （1）第一点：字符串必须是连续的，由这一点不难想到算法优化一定和双指针有关。

        （2）第二点：字符串必须是只包含一个字母，那么我们是不是可以转换思路：把原来存储字符串的哈希表改为存储每一个字母的哈希表呢？

好，根据这两点思考，思路大概就出来了，大概流程就是，先用双指针遍历一遍，将所有连续的字符串的长度存到哈希表中，这样再通过哈希表的值进行比较得出结果即可。

接下来就是问题关键所在：既然我们要求的是满足条件的最长字符串长度，那我们是不是贪心地把每一个字母能组成的最长字符串存下来就可以了呢？当然不是，下面就是一个反例：aaaabbbabaaa    这个样子的一个字符串， 如果我们只存每个字母的最长字符串，这样a最长就是4，b最长就是3，由题意可得b出现最多的就是（3 - 2）就是1，a最长就是（4 - 2）就是2，但是如果把第二长的加上去一起考虑，那么可以在“aaaa”中取出两个“aaa”，在“aaa”中取出一个：aaa“，这样的话最大长度就是3，由此证明贪心策略是错的。

为什么要减去一个2呢？一个长度为n的字符串，要得到三个不相等的等长的连续子序列，那么第一个子序列最多只能（n - 2）的长度，这个自己画一下图就不难理解啦~

那么既然不能只存最长的，那我们就把所有组成的全部存下来，仔细分析一下即可：

既然题目要求至少出现三次，那我们就先看前三个最长的

如图所示：

        如图所示，我们把每一个字母连续的字符串长度全部存下来，这样的话就可以分析出可以从a中前三大的字符串中求出结果，那么取一个max就是3，那么又有一个新问题，比如b，最多就只有两个字符串，那怎么去取呢，最好想象的情况就是分类讨论，但是不用这么麻烦，我们直接在每一个字母后面都加上两个0，这样的话也就相当于加上了两个空字符串进行比较，既然求的是最大值，那么加上空字符串自然是不影响的。

接下来还有一个情况，在讨论第二种情况的时候，我们考虑的是前两个字符串，如果第二个字符串长度和第一个一样会不会有变化呢？答案是不会，也是这样算，具体可以简化成：

min(maxLen - 1, seconfLen)

为什么这么写，如果maxLen == secondLen，那么就是在maxLen中取两个（maxLen - 1），在secondLen中取一个（maxLen - 1），这样长度就是（maxLen - 1），如图所示：

如果maxLen > secondLen，就是在secondLen中取出一个secondLen，然后在maxLen中至少可以取出两个secondLen，这样长度就是secondLen。

也就是说，如果secondLen < maxLen,那就是secondLen，反之则是（maxLen - 1），另外最大值只能取到maxLen - 1 和 secondLen的最小值，自己画图模拟就是很简单的逻辑。

这样就完成了核心的逻辑，至于取出前三个最大的值，可以线性枚举也可以排序，线性枚举的话时间复杂度要稍微低一点，但是随之而来的就是编码会复杂一些，所以我用的是排序的方法。

代码如下：

class Solution {
public:
    int maximumLength(string s) {
        vector<vector<int>> mp(26);
        int ans = -1, n = s.size();
        int left = 0, right = -1;
        while (++right < n) {
            while (right < n && s[right] == s[left]) {
                right++;
            }
            mp[s[left] - 'a'].push_back(right - left);
            left = right;
            --right;
        }
        // int cnt = 1;
        for (auto& arr : mp) {
            if (!arr.size()) continue;
            // cout << cnt++ << ": ";
            // for (auto& x : arr) cout << x << ' ';
            // cout << endl;
            arr.push_back(0); arr.push_back(0);
            sort(arr.begin(), arr.end(), [&](const int &a, const int &b) -> bool {
                return a > b;
            });
            int fir = arr[0], sec = arr[1], thr = arr[2];
            ans = max({ans, fir - 2, min(fir - 1, sec), thr});
        }
        return ans == 0 ? -1 : ans;
    }
};