至多包含 K 个不同字符的最长子串
难度:
标签:
题目描述
代码结果
运行时间: 46 ms, 内存: 16.3 MB
/*
* 题目思路：
* 使用Java Stream和函数式编程来实现这个问题的解决方案。由于Java Stream不适合直接处理滑动窗口问题，
* 我们将使用传统的方式结合Stream API来实现。我们同样维护一个滑动窗口，并使用哈希图记录字符频率。
*/
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
final int[] left = {0};
final int[] maxLength = {0};
Map<Character, Integer> map = new HashMap<>();
IntStream.range(0, s.length()).forEach(right -> {
char rightChar = s.charAt(right);
map.put(rightChar, map.getOrDefault(rightChar, 0) + 1);
while (map.size() > k) {
char leftChar = s.charAt(left[0]);
map.put(leftChar, map.get(leftChar) - 1);
if (map.get(leftChar) == 0) {
map.remove(leftChar);
}
left[0]++;
}
maxLength[0] = Math.max(maxLength[0], right - left[0] + 1);
});
return maxLength[0];
}
}解释
方法:
这个题解采用了滑动窗口的思路。使用两个指针 left 和 right 分别表示窗口的左右边界，types 表示当前窗口内不同字符的数量。通过移动右指针扩大窗口，当 types 超过 k 时，移动左指针缩小窗口，直到 types 不超过 k。在整个过程中，记录窗口的最大长度即可得到最终答案。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在处理字符计数时，为什么选择使用128大小的数组？这是否和特定字符编码有关？
▷🦆
为什么在遍历完字符串后直接返回`right - left + 1`作为结果，而不是在循环中更新一个最大长度的变量？
▷🦆
当`types`超过`k`时，通过移动左指针减少types的处理方式是否可能导致漏掉某些潜在的最长子串？
▷🦆
在使用滑动窗口策略时，如何确保所有可能的窗口都被检查过，特别是在字符串的末尾？
▷相关问题
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
替换后的最长重复字符
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。
示例 1：
输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。 可能存在其他的方法来得到同样的结果。
提示：
1 <= s.length <= 105s仅由大写英文字母组成0 <= k <= s.length
K 个不同整数的子数组
给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
- 例如，
[1,2,3,1,2]中有3个不同的整数：1，2，以及3。
子数组 是数组的 连续 部分。
示例 1：
输入：nums = [1,2,1,2,3], k = 2 输出：7 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
输入：nums = [1,2,1,3,4], k = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
提示：
1 <= nums.length <= 2 * 1041 <= nums[i], k <= nums.length
最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= nums.length <= 105nums[i]不是0就是10 <= k <= nums.length