题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串，由a、b、c组成，每次可以从最左侧或最右侧删除一个，求在每个字符至少删除 k 个的情况下，删除最少的数目。

思路分享

  • 从【Leetcode Daily】1658将x减到0的最小操作数这样的题中学到了，滑动窗口对于这种对最左侧和最右侧操作的题，往往采用所谓的“逆向”思路，也就是最大化地“去除”，从而最后计算出结果。

  • 拿本题来说，可以先记录整个字符串的各个字符的数目，窗口的内容并非是记录最左侧或最右侧的删除，而是记录最左侧和最右侧操作完后，中间的部分，目标是最大化这部分，从而间接最小化所求数目。

代码解答（强烈建议自行解答后再看）

  • 陆爻齐的参考解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int takeCharacters(string s, int k) {
        int *rec = new int[3]();
        for (const char c : s) {
            rec[c-'a']++;
        }
        if (rec[0] < k || rec[1] < k || rec[2] < k) return -1;
        //cout << rec[0] << " " << rec[1] << " " << rec[2] << endl;
        int left = 0;
        int win = 0;
        for (int i = 0; i < s.size(); i++) {
            rec[s[i]-'a']--;
            while(rec[0] < k || rec[1] < k || rec[2] < k) {
                //cout << "update:" << "i:" << i << ";left:" << left << endl;
                rec[s[left++]-'a']++;
            }
            
            //cout << rec[0] << " " << rec[1] << " " << rec[2] << endl;
            if (rec[0] >= k && rec[1] >= k && rec[2] >= k) {
                //cout << "result:" << "i:" << i << ";left:" << left << endl;
                win = max(win, i-left+1);
            }
        }
        return s.size()-win;
    }
};