[LeetCode] 2516. Take K of Each Character From Left and Right

You are given a string s consisting of the characters ‘a’, ‘b’, and ‘c’ and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

Example 1:
Input: s = “aabaaaacaabc”, k = 2
Output: 8
Explanation:
Take three characters from the left of s. You now have two ‘a’ characters, and one ‘b’ character.
Take five characters from the right of s. You now have four ‘a’ characters, two ‘b’ characters, and two ‘c’ characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:
Input: s = “a”, k = 1
Output: -1
Explanation: It is not possible to take one ‘b’ or ‘c’ so return -1.

Constraints:
1 <= s.length <= 105
s consists of only the letters ‘a’, ‘b’, and ‘c’.
0 <= k <= s.length

每种字符至少取 K 个。

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

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

思路

思路是滑动窗口。这道题要求我们只能从 input 两侧拿字母，那么 s 的中间部分就是连续的，所以这里我们可以用滑动窗口。

首先我们统计一下 s 中原来有的 a, b, c 三种字符的个数分别有多少。一个需要排除的 corner case 是如果这三个字母有任何一个字母的出现次数已经不足 k 了，则直接返回 -1。

接着我们可以开始用滑动窗口的模板遍历 input 数组了。end 指针往右边走的时候，start 和 end 中间包含的字母数量是越多的，那么此时我们可以把 start 和 end 组成的这个窗口理解为留下的字母个数。那么不包含在这个窗口内的字母就是从 input 字符串两侧被移除的字母。此时如果有任何一个字母被移除的次数大于等于 k（反之就是在窗口内的个数小于 k）的时候，我们就要移动 start 指针。

注意这道题我们要找一个尽可能大的窗口，以为题目求的是一个尽可能小的分钟数。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();
        int[] map = new int[3];
        for (char c : s.toCharArray()) {
            map[c - 'a']++;
        }
        for (int i = 0; i < 3; i++) {
            if (map[i] < k) {
                return -1;
            }
        }

        int res = 0;
        int start = 0;
        int end = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            map[c1 - 'a']--;
            end++;
			// 窗口外的字母不足k个，就要移动左指针了
            while (map[c1 - 'a'] < k) {
                char c2 = s.charAt(start);
                map[c2 - 'a']++;
                start++;
            }
            res = Math.max(res, end - start);
        }
        return n - res;
    }
}