2516. 每种字符至少取 K 个

Problem: 2516. 每种字符至少取 K 个

错误思路

看到从两边求解，我首先想到的是，先尝试贪心试试？每次如果某个字符未达到上限就取，在两边都没有时，哪边离得最近就取：但这样显然是不正确的。

接下来想到的是记忆化搜索或者说动态规划。但是这题又不大满足无后效性这一特点，前面的操作对于后面子字符串是有影响的。

于是我尝试了暴力搜索，但是效率太低，最后超时了。

正确思路

很多题目都不能直接从他本身的描述直接开始做，需要发掘其中的隐藏要点。本题中由于从两边考虑多种方法都难以求解，归根结底原因很大程度就是两边求解是不连续的，那么反过来想，中间的字符串不就是连续的吗？

而只要字符串是连续的，我们就可以自然而然想到双指针滑动窗口的解决方法。对于所给问题，实际上可以首先转为求解余下符合条件的最长中间子字符串，本质上也是对于每个要求的字符，要找出正好符合一定数量的字串。这样考虑双指针就很容易了，我们维护i到j为除去两端的中间子串，每次若j位置字符没有达到所需数量就自增j，否则自增i的位置，以减少j位置字符的计数，同时维护最长的中间字串长度，这样即可求解。

复杂度

• 时间复杂度: $O(n)$，遍历两次数组。
• 空间复杂度: $O(1)$，若干常量，和常量大小map。

Code

class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();
        char [] cs = s.toCharArray();
        Map<Character, Integer> m = new HashMap<>();
        m.put('a', -k);
        m.put('b', -k);
        m.put('c', -k);
        for (int i = 0; i < n; i++) {
            m.put(cs[i], m.get(cs[i]) + 1);
        }
        for (Integer value : m.values()) {
            if (value < 0) return -1;
        }
        int i = 0;
        int j = 0;
        int count = 0;
        while (i < n && j < n) {
            m.put(cs[j], m.get(cs[j]) - 1);
            while (i <= j && m.get(cs[j]) < 0) {
                m.put(cs[i], m.get(cs[i]) + 1);
                i++;
            }
            count = Math.max(count, j - i + 1);
            j++;
        }
        return n - count;
    }
}