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

🟠   🔖  哈希表 字符串 分治 滑动窗口  🔗 力扣 LeetCode

题目

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

if no such substring exists, return 0.

Example 1:

Input: s = "aaabb", k = 3

Output: 3

Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2

Output: 5

Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Constraints:

• 1 <= s.length <= 10^4
• s consists of only lowercase English letters.
• 1 <= k <= 10^5

题目大意

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

如果不存在这样的子字符串，则返回 0。

示例 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

解题思路

1. 字符种类限制的优化策略

   • 不必暴力枚举所有子串，而是以 字符种类数量 (targetUnique) 为目标，从 1 到字符串中实际字符种类数进行滑动窗口遍历。
   • charLen 是 s 中去重字符的数量，通过 new Set(s.split('')) 来计算。

2. 滑动窗口机制

   • 左右双指针 (left 和 right)：动态控制子串范围。
   • 字符计数 (charCount) 哈希表：记录当前窗口内字符的出现次数。
   • 状态变量 (uniqueCount, countAtLeastK)：
     • uniqueCount：窗口中不同字符的数量。
     • countAtLeastK：出现次数至少为 k 的字符数量。

3. 窗口调整规则

   • 每次向右扩展窗口时更新字符计数和状态变量。
   • 如果 uniqueCount > targetUnique，说明窗口内字符种类超出目标范围，需要移动左指针收缩窗口。
   • 如果 uniqueCount == countAtLeastK，更新结果长度。

复杂度分析

• 时间复杂度：O(26 * n)
  • 外层循环最多 26 次（针对每种字符种类数量）。
  • 内层滑动窗口处理时间复杂度为 O(n)。
• 空间复杂度：O(26)，用于字符计数哈希表 charCount。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstring = function (s, k) {
	if (!s || s.length === 0) return 0;
	let maxLen = 0;
	const n = s.length;
	const charLen = new Set(s.split('')).size;

	for (let targetUnique = 1; targetUnique <= charLen; targetUnique++) {
		let left = 0,
			right = 0;
		const charCount = new Map();
		let uniqueCount = 0,
			countAtLeastK = 0;

		while (right < n) {
			// 扩展窗口
			const charRight = s[right];
			charCount.set(charRight, (charCount.get(charRight) || 0) + 1);
			if (charCount.get(charRight) === 1) uniqueCount++;
			if (charCount.get(charRight) === k) countAtLeastK++;
			right++;

			// 收缩窗口
			while (uniqueCount > targetUnique) {
				const charLeft = s[left];
				if (charCount.get(charLeft) === k) countAtLeastK--;
				charCount.set(charLeft, charCount.get(charLeft) - 1);
				if (charCount.get(charLeft) === 0) uniqueCount--;
				left++;
			}

			// 更新结果
			if (uniqueCount === countAtLeastK) {
				maxLen = Math.max(maxLen, right - left);
			}
		}
	}

	return maxLen;
};

相关题目

题号	标题	题解	标签	难度	力扣
2014	重复 K 次的最长子序列		贪心 字符串 回溯 2+	🔴	🀄️ 🔗
2067	等计数子串的数量 🔒		字符串 计数 前缀和	🟠	🀄️ 🔗
2405	子字符串的最优划分	[✓]	贪心 哈希表 字符串	🟠	🀄️ 🔗
2958	最多 K 个重复元素的最长子数组		数组 哈希表 滑动窗口	🟠	🀄️ 🔗
2981	找出出现至少三次的最长特殊子字符串 I		哈希表 字符串 二分查找 2+	🟠	🀄️ 🔗
2982	找出出现至少三次的最长特殊子字符串 II		哈希表 字符串 二分查找 2+	🟠	🀄️ 🔗