LeetCode 补充题 179. 含至少 k 个相同字符的最短子串
题目描述
[!green]
牛客原题： ✅ eli和字符串
给定小写英文字符串
s和正整数k，找出最短的连续子串，使其中某一种字母至少出现k次。返回该子串的长度；不存在时返回
-1。
示例 1：
输入：
s = "abeba", k = 2
输出：3
解释： 子串"beb"长度为 3，其中b出现两次；不存在满足条件的更短子串。
提示：
- 字符串只含小写英文字母，
k为正整数。 - 只要求某一种字母出现至少
k次，不要求所有字母都满足。 - 无解返回
-1。
题意分析
只要求某一种字母出现至少
k次，其他字符不受限制。对一个满足要求的区间，可以去掉目标字母首次出现前、末次出现后的字符，所以最短候选的两端一定是该字母的出现位置。
解法：每种字母最近 k 次出现的跨度
核心思路
[!blue]
为 26 种字母分别保存递增的出现下标。当前读到某字母的第
t次出现，右端固定为i时，最靠右且仍包含k次出现的左端是第t-k+1次出现的位置，即列表下标size-k。候选长度为
i - positions[size-k] + 1。选更早的出现位置只会让区间更长，选更晚的位置又不足k次，因此这个候选就是固定当前右端的最短合法区间。枚举所有字母的全部右端，便覆盖全局最优。每次只追加一个位置并检查一个候选，总工作量为线性。
k == 1且字符串非空时得到长度 1；没有字母出现达到k次时保留无解标记，最后返回 -1。
解题步骤
- 为 26 种字母各保存按顺序追加的出现位置。
- 某字母出现数量达到 k 后，取最近 k 次中的首尾下标计算跨度。
- 更新全部候选的最短长度，没有候选则返回 -1。
代码实现
class Solution {
public int shortest(String s, int k) {
if (k <= 0) {
throw new IllegalArgumentException("k must be positive");
}
ArrayList<Integer>[] positions = new ArrayList[26];
for (int i = 0; i < 26; i++) {
positions[i] = new ArrayList<>();
}
int answer = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); i++) {
ArrayList<Integer> p = positions[s.charAt(i) - 'a'];
p.add(i);
if (p.size() >= k) {
answer = Math.min(answer, i - p.get(p.size() - k) + 1);
}
}
return answer == Integer.MAX_VALUE ? -1 : answer;
}
}
func shortest(s string, k int) int {
if k <= 0 {
panic("k must be positive")
}
var positions [26][]int
answer := len(s) + 1
for i := 0; i < len(s); i++ {
c := s[i] - 'a'
positions[c] = append(positions[c], i)
p := positions[c]
if len(p) >= k {
answer = min(answer, i-p[len(p)-k]+1)
}
}
if answer == len(s)+1 {
return -1
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
固定某次出现为右端时，最近 k 次出现给出最靠右的合法左端，从而得到该右端的最短候选。
易错点总结
[!yellow]
要求某一种字母达到k次，不是每种字母都达到k次；窗口内可以含其它字母。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 固定目标字母并将匹配位置视为 1，其余位置视为 0，寻找至少 k 次出现就转为最短达标区间；本题直接保存最近 k 次出现的位置，省去逐个缩短左边界。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！