怎么用网站推广_广州开发区管委会官网_网站搜索量查询_第一站长网

大家好，欢迎来到无限大的频道

今天继续给大家带来每日一题

题目描述（中等）：

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

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。

在这里插入图片描述

题目分析

题目给定一个由字符 ‘a’, ‘b’, ‘c’ 组成的字符串 s 和一个非负整数 k。你需要从字符串的左侧或右侧每次取一个字符，取走每种字符至少 k 个，返回这个操作所需的最少分钟数。如果无法完成操作，则返回 -1。

解题思路

需求分析：
- 要求我们至少取走 k 个 ‘a’、‘k’ 个 ‘b’、‘k’ 个 ‘c’。
- 直接从字符串的两端取字符，需要在保证符合条件的前提下，尽量减少取走的总字符数。
预检查：
- 首先遍历字符串，统计各个字符的总数量。
- 如果任何一种字符的数量小于 k，则直接返回 -1，因为不可能完成任务。
滑动窗口：
- 既然必须从两端取字符，我们可以尝试计算从一端取出所有字符的最小代价。
- 使用双指针技巧构建一个滑动窗口，每次移动两个指针来记录两个端点的位置。
- 每当右端点 r 多取一个字符时，减少该字符的需求量 cnt。若不足 k，通过移动左端点 l来补充字符，直到满足每种字符的需求量。
结果计算：
- 滑动窗口的右指针遍历完整个字符串的过程，可以计算出满足需求情况下，最少需要保留的字符串长度，即 len - (r - l + 1)。
- 在满足需求的条件下，记录保留字串的最小长度，我们的答案是在字符串 len 中取出剩余部分所需的最少字符数，即 len - (r - l + 1)。

算法设计

初始化字符计数数组 cnt[3]。
统计字符串中各个字母的总数量。
判断是否有无法完成的字符种类，直接返回 -1。
使用双指针方法：
- 初始状态下，双指针指向左端 l = 0，同时 r 从头开始遍历。
- 对于每个右端 r，减少该字符的需求量。
- 当某种字符需求量不足时，移动左端 l 补充字符需求。
- 在满足条件的时候，更新答案为 ans = min(ans, len - (r - l + 1))。
返回计算出的最小值。

参考代码如下

int takeCharacters(char* s, int k) {int cnt[3] = {0};int len = strlen(s);int ans = len;for (int i = 0; i < len; i++) {cnt[s[i] - 'a']++;}if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {ans = len;} else {return -1;}for (int l = 0, r = 0; r < len; r++) {cnt[s[r] - 'a']--;while (l < r && (cnt[0] < k || cnt[1] < k || cnt[2] < k)) {cnt[s[l] - 'a']++;l++;}if (cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) {ans = fmin(ans, len - (r - l + 1));}}return ans;
}

时间复杂度分析

初始化计数和预检查：需要遍历一遍字符串，复杂度为 ( O(n) )。
滑动窗口的操作：最坏情况下，l 和 r 各遍历一次字符串，时间复杂度是 ( O(n) )。
总时间复杂度：综上，算法的总时间复杂度为 ( O(n) )。

空间复杂度分析

仅使用了固定数量的额外空间（字符计数数组 cnt[3]），所以空间复杂度为 ( O(1) )。