2516. 每种字符至少取 K 个

🟠   🔖  哈希表 字符串 滑动窗口  🔗 力扣 LeetCode

题目

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return _theminimum number of minutes needed for you to take at least _k of each character, or return-1 if it is not possible to takek of each character.

Example 1:

Input: s = "aabaaaacaabc", k = 2

Output: 8

Explanation:

Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.

Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.

A total of 3 + 5 = 8 minutes is needed.

It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1

Output: -1

Explanation: It is not possible to take one 'b' or 'c' so return -1.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only the letters 'a', 'b', and 'c'.
• 0 <= k <= s.length

题目大意

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

解题思路

1. 统计每种字符的总数

首先，遍历字符串 s 统计 'a'、'b' 和 'c' 的总数量 total，分别存储在数组 total 中。

如果任何一种字符的总数量小于 k，直接返回 -1，因为无法满足题目要求。

2. 逆向考虑剩余的区间

要求最短的前缀和后缀，即最长的中间连续子数组的长度，满足：中间子数组中每种字符的数量不超过 total[i] - k。

这是因为，从整个字符串中去掉满足条件的中间部分后，剩下的前缀和后缀的字符数量必然满足要求。

3. 使用滑动窗口找到最长中间子数组

通过滑动窗口维护一个计数数组 window，统计当前窗口内每种字符的数量：

• 窗口右边界 right 每次向右扩展，增加字符的计数；
• 当窗口内某种字符数量超过允许值 total[i] - k 时，移动左边界 left 缩小窗口；
• 每次更新窗口长度 right - left 并与结果 res 比较，取最短的前缀和后缀长度。

4. 结果计算

对于窗口中满足条件的最长中间子数组，剩余的前缀和后缀长度为 n - (right - left)，记录最小值。

最后返回 res。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，需要遍历两次字符串，统计字符总数一次，滑动窗口一次。
• 空间复杂度：O(1)，使用了常数级别的数组存储字符统计。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var takeCharacters = function (s, k) {
	let total = [0, 0, 0]; // 统计字符 'a', 'b', 'c' 的总数
	for (let char of s) {
		total[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
	}

	// 如果任意一种字符不足 k 个，返回 -1
	if (total[0] < k || total[1] < k || total[2] < k) {
		return -1;
	}

	const n = s.length;
	let window = [0, 0, 0]; // 当前窗口中字符的数量
	let res = n; // 结果初始化为字符串长度
	let left = 0;
	let right = 0;

	// 滑动窗口
	while (right < n) {
		// 扩展右边界
		window[s.charCodeAt(right) - 'a'.charCodeAt(0)]++;
		right++;

		// 收缩左边界，使得窗口内字符数量满足条件
		while (
			window[0] > total[0] - k ||
			window[1] > total[1] - k ||
			window[2] > total[2] - k
		) {
			window[s.charCodeAt(left) - 'a'.charCodeAt(0)]--;
			left++;
		}

		// 更新结果：最短前缀和后缀长度
		res = Math.min(res, n - (right - left));
	}

	return res; // 返回结果
};

相关题目

题号	标题	题解	标签	难度	力扣
88	合并两个有序数组	[✓]	数组 双指针 排序	🟢	🀄️ 🔗
143	重排链表	[✓]	栈 递归 链表 1+	🟠	🀄️ 🔗
1652	拆炸弹	[✓]	数组 滑动窗口	🟢	🀄️ 🔗