Leetcode 2516. Take K of Each Character From Left and Right

[Woodyiiiiiii]

这道题一开始我先入为主，想用双指针，但无从下手。

最后改为滑动窗口了。其实滑动窗口也是双指针的一种。

使窗口滑动，尽量使得窗口外的数组长度变小，但又满足题目条件，每个字母的出现次数都要大于等于k。

而且，发现这种可以两头取数无限次的题型，是在暗示用滑动窗口/双指针的思想——转变思维， 求内部中间面积的变化。

class Solution {
    public int takeCharacters(String s, int k) {
        Map<Character, Integer> cntMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            cntMap.put(c, cntMap.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < 3; ++i) {
            char ch = (char) ('a' + i);
            if (cntMap.getOrDefault(ch, 0) < k) {
                return -1;
            }
        }
        if (k == 0) return 0;

        int l = 0, r = 0;
        int ans = s.length();
        while (r < s.length()) {
            char c = s.charAt(r);
            cntMap.put(c, cntMap.get(c) - 1);

            while ((cntMap.get('a') < k || cntMap.get('b') < k || cntMap.get('c') < k) && l <= r) {
                char c2 = s.charAt(l);
                cntMap.put(c2, cntMap.get(c2) + 1);
                l++;
            }

            if (l <= r) {
                ans = Math.min(ans, l + s.length() - r - 1);
            }
            ++r;
        }

        return ans;
    }
}

---

• https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/description/