深入理解：每种字符至少取 K 个的双指针解法

1. 问题回顾

给定一个由字符 ‘a’、’b’、’c’ 组成的字符串 s 和一个非负整数 k。每分钟，你可以选择取走 s 最左侧或最右侧的字符。你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1。

例如：s = “aabaaaacaabc”, k = 2

2. 算法核心思想

这个算法的核心思想是：

  1. 先从右边取足够的字符，确保满足条件。
  2. 然后尝试从左边取字符，同时减少右边取的字符，看是否能得到更优的解。

本质上，我们在寻找一个最长的中间子串，使得剩下的字符（两端的字符）满足每种字符至少 k 个的条件。

3. 详细步骤解析

让我们用例子 s = “aabaaaacaabc”, k = 2 来详细解释每一步：

  1. 初始化阶段：
    • 从右向左遍历，直到满足条件：
      “aabaaaacaa[bc]” （方括号内的字符是我们取的）
    • 此时 j = 10，初始答案 ans = 12 - 10 = 2
  2. 优化阶段：

… （继续这个过程）

  1. - i = 0: 取左边的 'a'

“[a]abaaaacaa[bc]”
无法减少右边的字符，ans 仍为 3

  1. - i = 1: 再取一个 'a'

“[aa]baaaacaa[bc]”
仍无法减少右边的字符，ans 仍为 4

  1. - i = 2: 取 'b'

“[aab]aaaacaa[bc]”
现在可以减少右边的 ‘b’
“[aab]aaaacaa[c]”
ans 更新为 4 (左3 + 右1)

  1. - i = 3: 取 'a'

“[aaba]aaacaa[c]”
ans 仍为 5

  1. - 最终找到最优解：ans = 4

4. 图解算法流程

让我们用一个简单的图来可视化这个过程：

  1. 初始状态：
  2. aabaaaacaabc
  3.           ^^  (j = 10, ans = 2)
  5. 优化过程：
  6. [a]abaaaacaabc
  7.           ^^  (i = 0, j = 10, ans = 3)
  9. [aa]baaaacaabc
  10.           ^^  (i = 1, j = 10, ans = 4)
  12. [aab]aaaacaa[c]
  13.            ^   (i = 2, j = 11, ans = 4)  ← 最优解
  15. [aaba]aaacaa[c]
  16.            ^   (i = 3, j = 11, ans = 5)
  18. ...

5. 代码解释

现在让我们再看一下代码，并解释每一部分：

  1. func takeCharacters(s string, k int) int {
  2.     n := len(s)
  3.     cnt := [3]int{}
  4.     j := n
  6.     // 初始化阶段：从右向左取字符
  7.     for cnt[0] < k || cnt[1] < k || cnt[2] < k {
  8.         if j == 0 {
  9.             return -1   // 无法满足条件
  10.         }
  11.         j--
  12.         cnt[s[j] - 'a'] ++
  13.     }
  15.     ans := n - j  // 初始答案
  17.     // 优化阶段：尝试从左边取字符
  18.     for i := 0; i < n && j < n; i++ {
  19.         cnt[s[i] - 'a']++  // 取左边的字符
  21.         // 尝试减少右边取的字符
  22.         for j < n && cnt[s[j]-'a'] > k {
  23.             cnt[s[j] - 'a'] --
  24.             j++
  25.         }
  27.         // 更新答案
  28.         ans = min(ans, i+1+n-j)
  29.     }
  31.     return ans
  32. }
  • 初始化阶段确保我们至少有一个可行解。
  • 优化阶段通过移动左指针 i，同时调整右指针 j，来寻找更优的解。
  • 内层的 for 循环确保我们始终满足条件，同时尽可能减少右边取的字符数。

6. 总结与思考

这个算法的巧妙之处在于：

  1. 它将问题转化为寻找最长的中间子串。
  2. 使用双指针技术，避免了暴力枚举所有可能性。
  3. 通过贪心的方式，每次都尝试找到当前最优解。

在实际编程中，这种思路非常有启发性。它告诉我们：

  • 有时候，从问题的一端开始，然后逐步优化，可能比直接寻找全局最优解更容易。
  • 双指针技术在处理字符串或数组问题时非常有用，特别是在需要考虑两端元素的情况下。
  • 将复杂问题转化为更容易理解和解决的形式，是解决算法问题的关键技巧之一。