每种字符至少取 K 个
难度:
标签:
题目描述
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 the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k 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 <= 105sconsists of only the letters'a','b', and'c'.0 <= k <= s.length
代码结果
运行时间: 152 ms, 内存: 16.4 MB
// Solution in Java using Java Streams
// This solution uses Java Streams to count characters and determine the minimum minutes.
import java.util.stream.IntStream;
public class Solution {
public int minMinutes(String s, int k) {
int n = s.length();
int[] left = new int[3];
int[] right = new int[3];
int l = 0, r = n - 1, total = 0;
while (l <= r) {
// Count left side
if (l < n) {
left[s.charAt(l) - 'a']++;
l++;
if (IntStream.of(left).allMatch(x -> x >= k)) break;
}
// Count right side
if (r >= 0) {
right[s.charAt(r) - 'a']++;
r--;
if (IntStream.of(right).allMatch(x -> x >= k)) break;
}
}
// Check if we can meet the requirement
if (IntStream.of(left).anyMatch(x -> x < k) || IntStream.of(right).anyMatch(x -> x < k)) return -1;
// Calculate the minimum moves
total = (l + (n - r - 1));
return total;
}
}
解释
方法:
题解采用滑动窗口的方法来找出最短的子数组，使得移除这个子数组后剩余的字符串中每个字符的数量都至少为k。首先计算字符串中每个字符'a'、'b'、'c'的总数减去k，得到a、b、c。如果任何一个字符的总数不足k，则直接返回-1，因为无法满足条件。接着使用一个滑动窗口（通过两个指针i和j定义），遍历字符串，统计窗口中各个字符的数量。如果窗口中某个字符的数量超过了所需的最小数量（比如'a'超过a），则尝试缩小窗口（移动左指针i）以找到最小的满足条件的窗口。最后，计算除去这个窗口外的剩余部分的长度，即为所需的最少分钟数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
如何确定滑动窗口中每个字符的最小数量阈值，即变量a、b、c是如何计算得出的？
▷🦆
题解中提到如果某个字符的总数不足k，则返回-1。这个判断是否在整个字符串被遍历前就可以确定？
▷🦆
题解中使用的滑动窗口策略是尝试找到最小的窗口使得移除这个窗口后剩余部分的每种字符都至少有k个。请问为什么不直接从字符串的两端开始移除字符来尝试满足条件？
▷🦆
在滑动窗口中，为什么在确定窗口内某个字符的数量超过所需时，就缩小窗口而不是继续拓展窗口？
▷