力扣题解2516

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

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

题目描述（中等）：

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

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

题目分析

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

解题思路

1. 需求分析：

   • 要求我们至少取走 k 个 ‘a’、‘k’ 个 ‘b’、‘k’ 个 ‘c’。
   • 直接从字符串的两端取字符，需要在保证符合条件的前提下，尽量减少取走的总字符数。

2. 预检查：

   • 首先遍历字符串，统计各个字符的总数量。
   • 如果任何一种字符的数量小于 k，则直接返回 -1，因为不可能完成任务。

3. 滑动窗口：

   • 既然必须从两端取字符，我们可以尝试计算从一端取出所有字符的最小代价。
   • 使用双指针技巧构建一个滑动窗口，每次移动两个指针来记录两个端点的位置。
   • 每当右端点 r 多取一个字符时，减少该字符的需求量 cnt。若不足 k，通过移动左端点 l来补充字符，直到满足每种字符的需求量。

4. 结果计算：

   • 滑动窗口的右指针遍历完整个字符串的过程，可以计算出满足需求情况下，最少需要保留的字符串长度，即 len - (r - l + 1)。
   • 在满足需求的条件下，记录保留字串的最小长度，我们的答案是在字符串 len 中取出剩余部分所需的最少字符数，即 len - (r - l + 1)。

算法设计

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

参考代码如下

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) )。

原文地址：https://blog.csdn.net/wxdzuishaui/article/details/142594541

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！