What is the sliding window technique?

The sliding window technique is a method used to maintain a subset of elements in a sequence, allowing efficient updates as the window moves through the data, often used for substring or subarray problems.

How do I know if it’s possible to take k of each character?

First, count the frequency of each character in the string. If any character’s frequency is less than k, it’s impossible to take k occurrences, and you should return -1.

What if the string contains characters other than 'a', 'b', and 'c'?

This problem specifically assumes the string only contains 'a', 'b', and 'c'. For strings containing other characters, the problem would need to be modified.

How does GhostInterview assist with the sliding window technique?

GhostInterview provides guidance on how to maintain the sliding window’s state, ensuring efficient character counting and helping you solve the problem step by step.

What is the optimal time complexity for this problem?

The optimal time complexity is O(n), where n is the length of the string. This is achieved by using the sliding window technique with efficient state management.

#2516

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

每种字符至少取 K 个

给你一个由字符 'a' 、 'b' 、 'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧还是最右侧的那个字符。你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。示例 1：输入： s = "aabaaaacaabc"…

哈希表字符串滑动窗口

题目描述

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

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

示例 1：

输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。

示例 2：

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。

提示：

1 <= s.length <= 10⁵
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

lightbulb

解题思路

方法一：滑动窗口

我们先用哈希表或者一个长度为 $3$ 的数组 $cnt$ 统计字符串 $s$ 中每个字符的个数，如果有字符的个数小于 $k$ 个，则无法取到，提前返回 $-1$ 。

题目要我们在字符串左侧以及右侧取走字符，最终取到的每种字符的个数都不少于 $k$ 个。我们不妨反着考虑问题，取走中间某个窗口大小的字符串，使得剩下的两侧字符串中，每种字符的个数都不少于 $k$ 个。

因此，我们维护一个滑动窗口，用指针 $j$ 和 $i$ 分别表示窗口的左右边界，窗口内的字符串是我们要取走的。我们每一次移动右边界 $i$ ，将对应的字符 $s[i]$ 加入到窗口中（也即取走一个字符 $s[i]$ ），此时如果 $cnt[s[i]]$ 个数小于 $k$ ，那么我们循环移动左边界 $j$ ，直到 $cnt[s[i]]$ 个数不小于 $k$ 为止。此时的窗口大小为 $i - j + 1$ ，更新最大窗口。

最终的答案就是字符串 $s$ 的长度减去最大窗口的大小。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        cnt = Counter(s)
        if any(cnt[c] < k for c in "abc"):
            return -1
        mx = j = 0
        for i, c in enumerate(s):
            cnt[c] -= 1
            while cnt[c] < k:
                cnt[s[j]] += 1
                j += 1
            mx = max(mx, i - j + 1)
        return len(s) - mx

speed

复杂度分析

指标	值
时间	O(n)
空间	O(3) = O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of sliding window technique and its relationship to character frequency counting.
question_mark
Evaluate the candidate’s ability to efficiently update the window state and maintain character counts.
question_mark
Check if the candidate can handle edge cases, like when k is greater than the number of occurrences of a character.

warning

常见陷阱

外企场景

error
Failing to check if k is feasible before attempting to process the string, which may lead to unnecessary computation.
error
Incorrectly managing the sliding window and failing to maintain accurate character counts across both ends of the string.
error
Overcomplicating the problem by using unnecessary data structures instead of the efficient sliding window with simple character counting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing this approach for strings with more than three characters.
arrow_right_alt
Extending this solution to handle varying values of k for different characters simultaneously.
arrow_right_alt
Optimizing for larger strings or strings with non-trivial distributions of characters.

help

常见问题

外企场景

继续练习

#2781 最长合法子字符串的长度 #2953 统计完全子字符串 #2981 找出出现至少三次的最长特殊子字符串 I