每种字符至少取 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 <= 105
s 仅由字母 ‘a’、‘b’、‘c’ 组成
0 <= k <= s.length
题解
题目要求从字符串左右两端取走字符,使取走的字符满足每种都大于等于 k 个,找到最少的取走的字符数
可以发现,我们取走的字符的补集,也就是中间剩下的字符,就是字符串的子串,而找到最少的取走的字符数,也就是找到满足条件的最长子串
这样问题就转换为寻找最长子串了,于是采用滑动窗口方法
我们用数组 arr[3] 统计窗口外面的各个字符的个数
假如数组中有数据小于 k 说明字符串不可能满足条件,直接返回 -1
接着我们遍历字符串,寻找最长的满足条件的子串
l=0,r=1 为窗口的边界,每想窗口中加入一个字符,数组 arr 中对应的字符数量 –
当数组中有数据小于 k 时,说明此时的窗口不符合条件,需要移动 l ,即 l++
当数组中的所有数据都大于等于 k 时,此时的子串的符合条件的,用max记录下最大的子串长度 r-l
最后返回的结果就是 strlen(s) - max
代码如下
int takeCharacters(char* s, int k) {
int arr[3]={0,0,0};
int n = strlen(s);
for(int i=0;i<n;i++)
{
arr[s[i]-'a']++;
}
for(int i=0;i<3;i++)
{
if(arr[i]<k)
{
return -1;
}
}
int l=0,r=1;
int max=-1;
arr[s[l]-'a']--;
while(r<n)
{
int f=1;
for(int i=0;i<3;i++)
{
if(arr[i]<k)
{
arr[s[l]-'a']++;
l++;
f=0;
}
}
if(f)
{
if(r-l>max)
{
max=r-l;
}
arr[s[r]-'a']--;
r++;
}
}
if(r-l>max && arr[0]>=k && arr[1]>=k && arr[2]>=k)
{
max=r-l;
}
return n-max;
}