LC 395. 至少有 K 个重复字符的最长子串

题目描述

这是 LeetCode 上的 395. 至少有 K 个重复字符的最长子串 ，难度为 中等。

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

提示：

• 1 <= s.length <= $10^4$
• s 仅由小写英文字母组成
• 1 <= k <= $10^5$

---

枚举 + 双指针

其实看到这道题，我第一反应是「二分」，直接「二分」答案。

但是往下分析就能发现「二分」不可行，因为不具有二段性质。

也就是假设有长度 t 的一段区间满足要求的话，t + 1 长度的区间是否「一定满足」或者「一定不满足」呢？

显然并不一定，是否满足取决于 t + 1 个位置出现的字符在不在原有区间内。

举个🌰吧，假设我们已经画出来一段长度为 t 的区间满足要求（且此时 k > 1），那么当我们将长度扩成 t + 1 的时候（无论是往左扩还是往右扩）：

• 如果新位置的字符在原有区间出现过，那必然还是满足出现次数大于 k，这时候 t + 1 的长度满足要求
• 如果新位置的字符在原有区间没出现过，那新字符的出现次数只有一次，这时候 t + 1 的长度不满足要求

因此我们无法是使用「二分」，相应的也无法直接使用「滑动窗口」思路的双指针。

因为双指针其实也是利用了二段性质，当一个指针确定在某个位置，另外一个指针能够落在某个明确的分割点，使得左半部分满足，右半部分不满足。

那么还有什么性质可以利用呢？这时候要留意数据范围「数值小」的内容。

题目说明了只包含小写字母（26 个，为有限数据），我们可以枚举最大长度所包含的字符类型数量，答案必然是 [1, 26]，即最少包含 1 个字母，最多包含 26 个字母。

你会发现，当确定了长度所包含的字符种类数量时，区间重新具有了二段性质。

当我们使用双指针的时候：

1. 右端点往右移动必然会导致字符类型数量增加（或不变）
2. 左端点往右移动必然会导致字符类型数量减少（或不变）

当然，我们还需要记录有多少字符符合要求（出现次数不少于 k），当区间内所有字符都符合时更新答案。

代码：

class Solution {
    public int longestSubstring(String s, int k) {
        int ans = 0;
        int n = s.length();
        char[] cs = s.toCharArray();
        int[] cnt = new int[26];
        for (int p = 1; p <= 26; p++) {
            Arrays.fill(cnt, 0);
            // tot 代表 [j, i] 区间所有的字符种类数量；sum 代表满足「出现次数不少于 k」的字符种类数量
            for (int i = 0, j = 0, tot = 0, sum = 0; i < n; i++) {
                int u = cs[i] - 'a';
                cnt[u]++;
                // 如果添加到 cnt 之后为 1，说明字符总数 +1
                if (cnt[u] == 1) tot++;
                // 如果添加到 cnt 之后等于 k，说明该字符从不达标变为达标，达标数量 + 1
                if (cnt[u] == k) sum++;
                // 当区间所包含的字符种类数量 tot 超过了当前限定的数量 p，那么我们要删除掉一些字母，即「左指针」右移
                while (tot > p) {
                    int t = cs[j++] - 'a';
                    cnt[t]--;
                    // 如果添加到 cnt 之后为 0，说明字符总数-1
                    if (cnt[t] == 0) tot--;
                    // 如果添加到 cnt 之后等于 k - 1，说明该字符从达标变为不达标，达标数量 - 1
                    if (cnt[t] == k - 1) sum--;
                }
                // 当所有字符都符合要求，更新答案
                if (tot == sum) ans = Math.max(ans, i - j + 1);
            }
        }
        return ans;
    }
}

• 时间复杂度：枚举 26 种可能性，每种可能性会扫描一遍数组。复杂度为 $O(n)$
• 空间复杂度：$O(n)$

---

总结 & 补充

【总结】：

「当确定了窗口内所包含的字符数量时，区间重新具有了二段性质」。这是本题的滑动窗口解法和迄今为止做的滑动窗口题目的最大不同，本题需要手动增加限制，即限制窗口内字符种类。

【补充】这里解释一下「为什么需要先枚举 26 种可能性」：

首先我们知道「答案子串的左边界左侧的字符以及右边界右侧的字符一定不会出现在子串中，否则就不会是最优解」。

但如果我们只从该性质出发的话，朴素解法应该是使用一个滑动窗口，不断的调整滑动窗口的左右边界，使其满足「左边界左侧的字符以及右边界右侧的字符一定不会出现在窗口中」，这实际上就是双指针解法，但是如果不先敲定（枚举）出答案所包含的字符数量的话，这里的双指针是不具有单调性的。

换句话说，只利用这一性质是没法完成逻辑的。

这时候我们面临的问题是：性质是正确的，但是还无法直接利用。

因此我们需要先利用字符数量有限性（可枚举）作为切入点，使得「答案子串的左边界左侧的字符以及右边界右侧的字符一定不会出现在子串中」这一性质在双指针的实现下具有单调性。也就是题解说的「让区间重新具有二段性质」。

然后遍历 26 种可能性（答案所包含的字符种类数量），对每种可能性应用滑动窗口（由上述性质确保正确），可以得到每种可能性的最大值（局部最优），由所有可能性的最大值可以得出答案（全局最优）。

---

点评

这道题的突破口分析其实和 1178. 猜字谜 类似。

解决思路：当我们采用常规的分析思路发现无法进行时，要去关注一下数据范围中「数值小」的值。因为数值小其实是代表了「可枚举」，往往是解题或者降低复杂度的一个重要（甚至是唯一）的突破口。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.395 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。