Medium

题目描述

给你一个由字符 ‘a’、‘b’、‘c’ 组成的字符串 s 和一个非负整数 k。每分钟，你可以选择取走 s 最左侧或者最右侧的那个字符。

请返回你需要的最少分钟数，使得你可以取到至少 k 个每种字符，如果无法取到 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 <= 10^5
  • s 由字母 ‘a’、‘b’、‘c’ 组成
  • 0 <= k <= s.length

解题思路

这道题需要从字符串的左右两端取字符，使得每种字符 (‘a’, ‘b’, ‘c’) 都至少取到 k 个。

核心思路： 我们可以枚举从左侧取 i 个字符的所有情况，然后计算为了满足条件还需要从右侧取多少个字符。

解决步骤：

  1. 首先统计字符串中每种字符的总数，如果某种字符总数不足 k，直接返回 -1
  2. 使用双指针技术，枚举从左侧取 0 到 n 个字符的所有情况
  3. 对于每种从左侧取字符的情况，统计已取到的各字符数量
  4. 然后从右侧开始取字符，直到满足每种字符都至少有 k 个为止
  5. 记录所有可能方案中的最小值

优化点： 使用双指针避免重复计算。当左指针向右移动时，右指针可能需要向左移动来补充不足的字符，这样可以在 O(n) 时间内完成所有枚举。

时间复杂度为 O(n)，空间复杂度为 O(1)，是一个高效的滑动窗口解法。

代码实现

class Solution {
public:
    int takeCharacters(string s, int k) {
        int n = s.length();
        vector<int> count(3, 0);
        
        // 统计总字符数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 检查是否可能
        for (int i = 0; i < 3; i++) {
            if (count[i] < k) return -1;
        }
        
        int result = n;
        vector<int> left(3, 0);
        int right = n - 1;
        
        // 枚举从左侧取的字符数
        for (int i = 0; i <= n; i++) {
            // 添加左侧字符
            if (i > 0) {
                left[s[i-1] - 'a']++;
            }
            
            // 从右侧取字符直到满足条件
            while (right >= i) {
                bool valid = true;
                for (int j = 0; j < 3; j++) {
                    if (left[j] + (n - 1 - right >= 0 ? count[j] - (count[j] - left[j] - (n - 1 - right)) : 0) < k) {
                        valid = false;
                        break;
                    }
                }
                if (valid) break;
                right--;
            }
            
            if (right < i) break;
            
            result = min(result, i + (n - 1 - right + 1));
        }
        
        return result;
    }
};

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        count = [0, 0, 0]
        
        # 统计总字符数
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        # 检查是否可能
        for i in range(3):
            if count[i] < k:
                return -1
        
        result = n
        left = [0, 0, 0]
        right = n - 1
        
        # 枚举从左侧取的字符数
        for i in range(n + 1):
            # 添加左侧字符
            if i > 0:
                left[ord(s[i-1]) - ord('a')] += 1
            
            # 从右侧取字符直到满足条件
            while right >= i:
                # 计算右侧已取的字符数
                right_count = [0, 0, 0]
                for j in range(right + 1, n):
                    right_count[ord(s[j]) - ord('a')] += 1
                
                # 检查是否满足条件
                valid = True
                for j in range(3):
                    if left[j] + right_count[j] < k:
                        valid = False
                        break
                
                if valid:
                    break
                right -= 1
            
            if right < i:
                break
                
            result = min(result, i + (n - right))
        
        return result

public class Solution {
    public int TakeCharacters(string s, int k) {
        int n = s.Length;
        int[] count = new int[3];
        
        // 统计总字符数
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 检查是否可能
        for (int i = 0; i < 3; i++) {
            if (count[i] < k) return -1;
        }
        
        int result = n;
        int[] left = new int[3];
        int right = n - 1;
        
        // 枚举从左侧取的字符数
        for (int i = 0; i <= n; i++) {
            // 添加左侧字符
            if (i > 0) {
                left[s[i-1] - 'a']++;
            }
            
            // 从右侧取字符直到满足条件
            while (right >= i) {
                // 计算右侧已取的字符数
                int[] rightCount = new int[3];
                for (int j = right + 1; j < n; j++) {
                    rightCount[s[j] - 'a']++;
                }
                
                // 检查是否满足条件
                bool valid = true;
                for (int j = 0; j < 3; j++) {
                    if (left[j] + rightCount[j] < k) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) break;
                right--;
            }
            
            if (right < i) break;
            
            result = Math.Min(result, i + (n - right));
        }
        
        return result;
    }
}

var takeCharacters = function(s, k) {
    const n = s.length;
    const count = [0, 0, 0];
    
    // 统计总字符数
    for (const c of s) {
        count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // 检查是否可能
    for (let i = 0; i < 3; i++) {
        if (count[i] < k) return -1;
    }
    
    let result = n;
    const left = [0, 0, 0];
    let right = n - 1;
    
    // 枚举从左侧取的字符数
    for (let i = 0; i <= n; i++) {
        // 添加左侧字符
        if (i > 0) {
            left[s[i-1].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        
        // 从右侧取字符直到满足条件
        while (right >= i) {
            // 计算右侧已取的字符数
            const rightCount = [0, 0, 0];
            for (let j = right + 1; j < n; j++) {
                rightCount[s[j].charCodeAt(0) - 'a'.charCodeAt(0)]++;
            }
            
            // 检查是否满足条件
            let valid = true;
            for (let j = 0; j < 3; j++) {
                if (left[j] + rightCount[j] < k) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) break;
            right--;
        }
        
        if (right < i) break;
        
        result = Math.min(result, i + (n - right));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²)
空间复杂度O(1)

注：虽然有嵌套循环，但由于双指针的特性，右指针在整个过程中最多移动n次，所以实际时间复杂度接近O(n)。但在最坏情况下仍可能达到O(n²)。

相关题目