福建疫情最新数据消息_石家庄网页制作_谷歌网页版入口在线_在什么网站可以免费

2516. 每种字符至少取 K 个

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

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

数据范围

• 1 <= s.length <= 105
• s 仅由字母 'a'、'b'、'c' 组成
• 0 <= k <= s.length

分析

本题有良好的二分性质，对于某一个$t$，小于$t$的分钟都无法满足，大于等于t的都可以满足，因此可以考虑二分答案

代码

class Solution {
public:const static int N = 1e5 + 5;int prea[N], preb[N], prec[N];int lasta[N], lastb[N], lastc[N];int n;bool check(int t, int k) {for(int i = 0; i <= t; i ++ ) {int na = prea[i] + lasta[n - (t - i) + 1];int nb = preb[i] + lastb[n - (t - i) + 1];int nc = prec[i] + lastc[n - (t - i) + 1];if(na >= k && nb >= k && nc >= k) return true;}return false;}int find(int l, int r, int k) {while(l < r) {int mid = (l + r) >> 1;if(check(mid, k)) r = mid;else l = mid + 1;}return l;}int takeCharacters(string s, int k) {n = s.size();for(int i = 1; i <= n; i ++ ) {prea[i] = prea[i - 1] + (s[i  - 1] == 'a' ? 1 : 0);preb[i] = preb[i - 1] + (s[i  - 1] == 'b' ? 1 : 0);prec[i] = prec[i - 1] + (s[i  - 1] == 'c' ? 1 : 0);}for(int i = n; i >= 1; i -- ) {lasta[i] = lasta[i + 1] + (s[i - 1] == 'a' ? 1 : 0);lastb[i] = lastb[i + 1] + (s[i - 1] == 'b' ? 1 : 0);lastc[i] = lastc[i + 1] + (s[i - 1] == 'c' ? 1 : 0);}if(prea[n] < k || preb[n] < k || prec[n] < k) return -1;int l = 0, r = n;int res = find(0, n, k);return res;}
};

---