[每日一题] 2982.找出出现至少三次的最长特殊子字符串II

2024 年 05 月 30 日

106 次浏览

1501字数

> https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-ii/description/?envType=daily-question&envId=2024-05-02

和昨天的区别就是数据量来到了 $5 \times 10^5$ ，用昨天的方法也是可以解的。

首先统计每个字母的所有连续子串的长度，并按从大到小排序，筛选出前三个最长的子串 (这里可以只开三个空间，用冒泡的思想保证有序，下面的代码图方便直接存下所有的然后 `sort`) 。要找出三个特殊子串，有以下三种情况：

1. 从最长的特殊子串 $S_0$ 中取出三个长度为 $S_0 - 2$ 的特殊子串。
2. 从最长的特殊子串 $S_0$ 和次长特殊子串 $S_1$ 中取出三个长度一样的特殊子串：
   - 如果 $S_0 = S_1$ ，则可以取三个长度为 $S_0 - 1$ 的特殊子串；
   - 如果 $S_0 > S_1$ ，那么可以取三个长度为 $S_1$ 的特殊子串。
3. 从前三长的特殊子串 $S_0, S_1, S_2$ 中各取一个长度为 $S_3$ 的特殊子串。

三种情况取最大值，即为所需的答案。特判答案为 0 的时候，需要返回 -1 。

代码实现的时候，在数组末尾加两个 0 ，就无需特判连续子串不足三个的情况了。

```c++
    int maximumLength(std::string s) {
        const int n = s.length();

int cnt = 1;
        std::vector<int> groups[26];
        for (int i = 1; i < n; i++, cnt++) {
            if (s[i] != s[i - 1]) {
                groups[s[i - 1] - 'a'].push_back(cnt);
                cnt = 0;
            }
        }
        groups[s[n - 1] - 'a'].push_back(cnt);

int res = 0;
        for (auto &group : groups) {
            if (group.empty())
                continue;

std::sort(group.begin(), group.end(), std::greater<int>());
            group.push_back(0);
            group.push_back(0);

res = std::max({res, group[0] - 2, std::min(group[0] - 1, group[1]), group[2]});
        }

return res == 0 ? -1 : res;
    }
```

- 时间复杂度：$O(nlogn)$ ，其中 $n$ 为字符串的长度。如果只维护前三的长度，可以做到 $O(n)$ 。
- 空间复杂度：$O(n)$ 。

最后修改：2024 年 05 月 30 日