LeetCode395至少有 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 <= 105

解题思路

方法一

分治

1. 递归最基本的是记住递归函数的含义（务必牢记函数定义）：本题的 longestSubstring(s, k) 函数表示的就是题意，即求一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 k。函数入参 s 是表示源字符串；k 是限制条件，即子字符串中每个字符最少出现的次数；函数返回结果是满足题意的最长子字符串长度。
2. 递归的终止条件（能直接写出的最简单 case）：如果字符串 s 的长度少于 kkk，那么一定不存在满足题意的子字符串，返回 0；
3. 调用递归（重点）：如果一个字符 c 在 s 中出现的次数少于 k 次，那么 s 中所有的包含 c 的子字符串都不能满足题意。所以，应该在 s 的所有不包含 c 的子字符串中继续寻找结果：把 s 按照 c 分割（分割后每个子串都不包含 c），得到很多子字符串 t；下一步要求 t 作为源字符串的时候，它的最长的满足题意的子字符串长度（到现在为止，我们把大问题分割为了小问题(s → t)）。此时我们发现，恰好已经定义了函数 longestSubstring(s, k) 就是来解决这个问题的！所以直接把 longestSubstring(s, k) 函数拿来用，于是形成了递归。
4. 未进入递归时的返回结果：如果 s 中的每个字符出现的次数都大于k 次，那么 s 就是我们要求的字符串，直接返回该字符串的长度。

class Solution {public int longestSubstring(String s, int k) {if (s.length() < k) return 0;HashMap<Character, Integer> counter = new HashMap();for (int i = 0; i < s.length(); i++) {counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);}for (char c : counter.keySet()) {if (counter.get(c) < k) {int res = 0;for (String t : s.split(String.valueOf(c))) {res = Math.max(res, longestSubstring(t, k));}return res;}}return s.length();}
}

方法二

枚举 + 双指针

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

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

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

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

当然，我们还需要记录有多少字符符合要求（出现次数不少于 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，说明字符总数 +1if (cnt[u] == 1) tot++;// 如果添加到 cnt 之后等于 k，说明该字符从不达标变为达标，达标数量 + 1if (cnt[u] == k) sum++;// 当区间所包含的字符种类数量 tot 超过了当前限定的数量 p，那么我们要删除掉一些字母，即「左指针」右移while (tot > p) {int t = cs[j++] - 'a';cnt[t]--;// 如果添加到 cnt 之后为 0，说明字符总数-1if (cnt[t] == 0) tot--;// 如果添加到 cnt 之后等于 k - 1，说明该字符从达标变为不达标，达标数量 - 1if (cnt[t] == k - 1) sum--;}// 当所有字符都符合要求，更新答案if (tot == sum) ans = Math.max(ans, i - j + 1);}}return ans;}
}