每种字符至少取 K 个

2516. 每种字符至少取 K 个

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int takeCharacters(string s, int k) { } };

rust 解法, 执行用时: 3 ms, 内存消耗: 2.3 MB, 提交时间: 2024-09-27 09:25:26

impl Solution {
    pub fn take_characters(s: String, k: i32) -> i32 {
        let mut cnt = [0; 3];
        for c in s.bytes() {
            cnt[(c - b'a') as usize] += 1; // 一开始，把所有字母都取走
        }
        if cnt[0] < k || cnt[1] < k || cnt[2] < k {
            return -1; // 字母个数不足 k
        }

        let mut mx = 0;
        let mut left = 0;
        let s = s.as_bytes();
        for (right, &c) in s.iter().enumerate() {
            let c = (c - b'a') as usize;
            cnt[c] -= 1; // 移入窗口，相当于不取走 c
            while cnt[c] < k { // 窗口之外的 c 不足 k
                cnt[(s[left] - b'a') as usize] += 1; // 移出窗口，相当于取走 s[left]
                left += 1;
            }
            mx = mx.max(right - left + 1);
        }
        (s.len() - mx) as _
    }
}

javascript 解法, 执行用时: 84 ms, 内存消耗: 58.3 MB, 提交时间: 2024-09-27 09:24:58

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var takeCharacters = function(s, k) {
    const ordA = 'a'.charCodeAt(0);
    const cnt = [0, 0, 0];
    for (const c of s) {
        cnt[c.charCodeAt(0) - ordA]++; // 一开始，把所有字母都取走
    }
    if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
        return -1; // 字母个数不足 k
    }

    let mx = 0, left = 0;
    for (let right = 0; right < s.length; right++) {
        let c = s[right].charCodeAt(0) - ordA;
        cnt[c]--; // 移入窗口，相当于不取走 c
        while (cnt[c] < k) { // 窗口之外的 c 不足 k
            cnt[s[left].charCodeAt(0) - ordA]++; // 移出窗口，相当于取走 s[left]
            left++;
        }
        mx = Math.max(mx, right - left + 1);
    }
    return s.length - mx;
};

cpp 解法, 执行用时: 26 ms, 内存消耗: 11.9 MB, 提交时间: 2024-09-27 09:18:52

class Solution {
public:
    int takeCharacters(string s, int k) {
        int cnt[3]{};
        for (char c : s) {
            cnt[c - 'a']++; // 一开始，把所有字母都取走
        }
        if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
            return -1; // 字母个数不足 k
        }

        int mx = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s[right] - 'a';
            cnt[c]--; // 移入窗口，相当于不取走 c
            while (cnt[c] < k) { // 窗口之外的 c 不足 k
                cnt[s[left] - 'a']++; // 移出窗口，相当于取走 s[left]
                left++;
            }
            mx = max(mx, right - left + 1);
        }
        return s.length() - mx;
    }
};

java 解法, 执行用时: 7 ms, 内存消耗: 44 MB, 提交时间: 2024-09-27 09:18:06

class Solution {
    public int takeCharacters(String S, int k) {
        char[] s = S.toCharArray();
        int[] cnt = new int[3];
        for (char c : s) {
            cnt[c - 'a']++; // 一开始，把所有字母都取走
        }
        if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
            return -1; // 字母个数不足 k
        }

        int mx = 0; // 子串最大长度
        int left = 0;
        for (int right = 0; right < s.length; right++) {
            int c = s[right] - 'a';
            cnt[c]--; // 移入窗口，相当于不取走 c
            while (cnt[c] < k) { // 窗口之外的 c 不足 k
                cnt[s[left] - 'a']++; // 移出窗口，相当于取走 s[left]
                left++;
            }
            mx = Math.max(mx, right - left + 1);
        }
        return s.length - mx;
    }
}

python3 解法, 执行用时: 728 ms, 内存消耗: 15.7 MB, 提交时间: 2023-01-03 11:36:53

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        c = Counter(s)
        if any(c[a] < k for a in 'abc'): return -1
        res = n = len(s)
        left = 0
        for right, ch in enumerate(s):
            c[ch] -= 1
            while any(c[a] < k for a in 'abc'):
                c[s[left]] += 1
                left += 1
            res = min(res, n - (right - left + 1))
        return res

golang 解法, 执行用时: 12 ms, 内存消耗: 5.3 MB, 提交时间: 2023-01-03 11:36:05

func takeCharacters(s string, k int) int {
	n := len(s)
	c, j := [3]int{}, n
	for c[0] < k || c[1] < k || c[2] < k {
		if j == 0 {
			return -1 // 所有字母都取也无法满足要求
		}
		j--
		c[s[j]-'a']++
	}
	ans := n - j // 左侧没有取字符
	for i := 0; i < n && j < n; i++ { // 双指针
		c[s[i]-'a']++
		for j < n && c[s[j]-'a'] > k { // 维护 j 的最大下标
			c[s[j]-'a']--
			j++
		}
		ans = min(ans, i+1+n-j)
	}
	return ans
}

func min(a, b int) int { if b < a { return b }; return a }

python3 解法, 执行用时: 568 ms, 内存消耗: 15.6 MB, 提交时间: 2023-01-03 11:33:54

'''
设从左侧取到第 i 个字符，从右侧取到第 j 个字符。
由于随着 i 的变大，j 也会单调变大，因此可以用双指针，一边从小到大枚举 i，一边维护 j 的最大位置（j 尽量向右移）。
对于左侧没有取字符的情况需要单独计算。
'''
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        j = n = len(s)
        c = Counter()
        while c['a'] < k or c['b'] < k or c['c'] < k:
            if j == 0: return -1  # 所有字母都取也无法满足要求
            j -= 1
            c[s[j]] += 1
        ans = n - j  # 左侧没有取字符
        for i, ch in enumerate(s):
            c[ch] += 1
            while j < n and c[s[j]] > k:  # 维护 j 的最大下标
                c[s[j]] -= 1
                j += 1
            ans = min(ans, i + 1 + n - j)
            if j == n: break
        return ans

上一题

下一题

详情