每种字符至少取 K 个

Azusa 2024/9/27 力扣每日一题双指针

难度：中等

给你一个由字符 '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 <= 105
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

今天这道题还是比较考验逆向思维的，最后也是看了题解才做出来。

题目要求从两边开始取字母，求abc三个字母都取到k个时，最小的取字母的次数是多少。

按照正常的思维，应该是采用贪心从两边开始取，但你会发现贪心并不适合，因为可能在后面取某个字符时，会顺便把其他字符取好了，这时贪心就变成小丑了~

例如在例1中，正常我要取2个a，肯定是优先取最左边的两个，因为只需要花费2步。但是在取c时，可以明显看出来是从右边往左取，并且取到2个c时，已经顺便把2个a取好了，所以前面取a花的2步就没有意义了。

如何解决这种情况呢？一开始我也没有想法，看了提示说使用双指针，我就往这方面靠，发现确实可以用双指针来记录左右的位置，但我想的却是一个错误的方向。

使用语言有点难描述我的思路，边看代码可能更好理解：

var takeCharacters = function(s, k) {
  const arr = ['a', 'b', 'c']
  let ans = 0, mp1 = 0, mp2 = s.length - 1
  // 按照顺序找字符并确定双指针的位置
  for(const c of arr) {
    let count = 0
    // 找出已走的区间包含当前字符的个数
    for(let i = 0; i < mp1; i++) {
        if (s[i] == c) {
            count++
        }
    }
    for(let i = mp2+1; i < s.length; i++) {
        if (s[i] == c) {
            count++
        }
    }
    let p1 = mp1, p2 = mp2
    // 双指针继续移动
    while(count < k) {
      const pp1 = s.indexOf(c, p1)
      const pp2 = s.lastIndexOf(c, p2)
      if (pp1 == -1 || pp2 == -1 || pp1 > pp2) {
        return -1
      }
      // 与下个字符之间的距离
      const delta1 = Math.abs(pp1 - p1)
      const delta2 = Math.abs(pp2 - p2)
      
      // 判断是左指针移动还是右指针移动，这里有坑
      if (delta1 < delta2) {
        p1 = pp1 + 1
      } else {
        p2 = pp2 - 1
      } 
      count++
    }
    // 记录下走最远的距离，查找下个字符时可以从这里开始找。 这里也有坑
    mp1 = Math.max(p1, mp1)
    mp2 = Math.min(p2, mp2)
  }
  return mp1 + (s.length - mp2 - 1)
};

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

大致思路就是按abc顺序来找到各k个字符，并一步一步缩小左右指针的距离。这里面有几个坑是我一开始没考虑到的：

按abc顺序来找，可能在找c的同时会把a或者b或者a和b都找齐了，使得前面记录的指针位置是无效的
如果左右指针指向的字符与下一个要查找的字符之间的距离是相等的，那么从左边走过去还是从右边走过去哪个是最优的？
我是根据样例1来展开自己的思路，没有考虑到更全面的情况

虽然思路错了，但也解决了大概90%的测试用例，不过错就是错了，看看题解。

题解的思路是逆向思维，既然我要使得走的步数最少，那么可以转换为求左右指针中间最长的区间。先记录下每个字符出现的次数（可以认为是左右俩区间每个字符出现的次数），如果某个字符出现次数达不到k次则返回-1。

如果都达到k次则继续分析，要使得区间最大，那最优解法是，当右指针r固定时，左指针l越靠左越好。

那么r可以从0开始往右增加，并且每次增加都需要减掉对应字符出现的次数，而l也不是每次都需要从0开始，而是根据是否满足条件来往右走的，因为要保证左右区间的字符出现次数大于等于k。只要一满足条件则立刻停止移动l，然后放任r往右继续走，扩大中间的区间。

代码如下：

var takeCharacters = function(s, k) {
  const cnt = [0, 0, 0]
  const len = s.length
  let ans = len
  for(const c of s) {
    cnt[c.charCodeAt() - 97]++
  }
  if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
    return -1
  }

  let l = 0
  for(let r = 0; r < len; r++) {
    // 被包在中间区间的字符需要减掉次数
    cnt[s[r].charCodeAt() - 97]--
    // 不满足条件的情况下，左指针移动
    while(l < r && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {
        // 在左右区间的字符出现个数，因为被减掉过，需要加回来
        cnt[s[l].charCodeAt() - 97]++
        l++
    }
    // 满足条件的情况下
    if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {
        // 总长度减掉中间区间的长度也就是左右两边区间的长度，取最小 
        ans = Math.min(ans, len - (r - l + 1))
    }
  }
  return ans
};

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
28
29

这里有个点是，这abc三个字符出现次数需要同时判断，不能和我那边一样分开判断，否则就会出现我上面的问题。

Azusa的博客

Choose mode

每种字符至少取 K 个

每种字符至少取 K 个