LeetCode 340. 至多包含 K 个不同字符的最长子串

题目描述

🔥 340. 至多包含 K 个不同字符的最长子串

给定一个字符串 s 和一个整数 k，找出至多包含 k 个不同字符的最长子串的长度。

示例 1： 输入：s = "eceba", k = 2 输出：3 解释："ece" 是符合题意的最长子串。

示例 2： 输入：s = "aa", k = 1 输出：2 解释："aa" 是符合题意的最长子串。

思路分析

我们可以使用滑动窗口的技巧来解决这个问题。具体思路如下：

  1. 使用两个指针 left 和 right 来表示当前窗口的范围。
  2. 使用一个哈希表来记录窗口内字符的频率。
  3. 当窗口内的不同字符数量超过 k 时，移动 left 指针，直到窗口内的不同字符数量不超过 k。
  4. 在每次移动 right 指针时，更新最长子串的长度。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func lengthOfLongestSubstringKDistinct(s string, k int) int {
	left, right := 0, 0
	charCount := make(map[byte]int)
	maxLength := 0

	for right < len(s) {
		// 将当前字符加入窗口
		charCount[s[right]]++

		// 如果窗口内的不同字符超过 k，移动左指针
		for len(charCount) > k {
			charCount[s[left]]--
			if charCount[s[left]] == 0 {
				delete(charCount, s[left])
			}
			left++
		}

		// 更新最长子串的长度
		maxLength = max(maxLength, right-left+1)
		right++
	}

	return maxLength
}

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2023/42200922
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！