2516. 每种字符至少取 K 个#

题目描述#

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k。每分钟，你可以选择取走 s 最左侧还是最右侧的那个字符。

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1。

核心思想#

正难则反：反向滑动窗口。

从左右两端取字符，等价于中间保留一个窗口。求最小取走字符数，等价于求最大可保留窗口长度。

统计每种字符总数，窗口内每种字符最多允许保留 total[char] - k 个。用滑动窗口找满足条件的最长窗口，答案即为 n - 最长窗口长度。

算法步骤#

统计 s 中 'a'、'b'、'c' 的总数
若任一字符总数 < k，返回 -1
计算每种字符在窗口内最多允许保留的数量：need[c] = total[c] - k
滑动窗口找最长合法窗口（窗口内每种字符 ≤ need）：
- 右端点扩展，加入字符
- 当某字符超过 need 时，收缩左端点
- 更新最大窗口长度
返回 n - 最长窗口长度

逐步举例#

以 s = "aabbbcc", k = 1 为例：

统计：a=2, b=3, c=2

need（窗口内最多允许）：a=1, b=2, c=1

right	s[right]	window	超 need?	收缩	left	max_len
0	a	a=1	否	—	0	1
1	a	a=2	a>1	l=1	1	1
2	b	a=1,b=1	否	—	1	2
3	b	a=1,b=2	否	—	1	3
4	b	a=1,b=3	b>2	l=3	3	3
5	c	b=2,c=1	否	—	3	3
6	c	b=2,c=2	c>1	l=6	6	3

最终 max_len = 3，答案 = 7 - 3 = 4。

验证：取走 s[0:3]="aab" 和 s[6:]="c"，共 4 个字符，含 a=2≥1, b=1≥1, c=1≥1 ✓。

复杂度分析#

时间复杂度：O(n)。统计 O(n)，滑动窗口 O(n)。
空间复杂度：O(1)。只维护 3 个字符的计数。

参考#

灵茶山艾府：每种字符至少取 K 个

代码实现#

1
from collections import Counter
2

3

4
class Solution:
5
    def takeCharacters(self, s: str, k: int) -> int:
6
        cnt = Counter(s)
7
        if any(cnt[c] < k for c in "abc"):
8
            return -1
9

10
        n = len(s)
11
        need = {c: cnt[c] - k for c in "abc"}
12
        window = {"a": 0, "b": 0, "c": 0}
13
        left = max_len = 0
14

15
        for right in range(n):
16
            window[s[right]] += 1
17
            while window[s[right]] > need[s[right]]:
18
                window[s[left]] -= 1
19
                left += 1
20
            max_len = max(max_len, right - left + 1)
21

22
        return n - max_len

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6

7
from solution import Solution
8

9

10
class TestTakeCharacters(unittest.TestCase):
11
    def test_example1(self):
12
        s = "aabaaaacaabc"
13
        k = 2
14
        self.assertEqual(Solution().takeCharacters(s, k), 8)
15

16
    def test_example2(self):
17
        s = "a"
18
        k = 1
19
        self.assertEqual(Solution().takeCharacters(s, k), -1)
20

21
    def test_k_zero(self):
22
        s = "abc"
23
        k = 0
24
        self.assertEqual(Solution().takeCharacters(s, k), 0)
25

26
    def test_all_take(self):
27
        s = "aabbcc"
28
        k = 2
29
        self.assertEqual(Solution().takeCharacters(s, k), 6)
30

31
    def test_partial(self):
32
        s = "abc"
33
        k = 1
34
        self.assertEqual(Solution().takeCharacters(s, k), 3)
35

36
    def test_single_char(self):
37
        s = "aaaa"
38
        k = 2
39
        self.assertEqual(Solution().takeCharacters(s, k), -1)
40

41

42
if __name__ == "__main__":
43
    unittest.main()