力扣9.27

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，小于                                   t                              t                  t的分钟都无法满足，大于等于t的都可以满足，因此可以考虑二分答案
代码

1. class Solution {
2. public:
3.     const static int N = 1e5 + 5;
4.     int prea[N], preb[N], prec[N];
5.     int lasta[N], lastb[N], lastc[N];
6.     int n;
7.     bool check(int t, int k) {
8.         for(int i = 0; i <= t; i ++ ) {
9.             int na = prea[i] + lasta[n - (t - i) + 1];
10.             int nb = preb[i] + lastb[n - (t - i) + 1];
11.             int nc = prec[i] + lastc[n - (t - i) + 1];
12.             if(na >= k && nb >= k && nc >= k) return true;
13.         }
14.         return false;
15.     }
16.     int find(int l, int r, int k) {
17.         while(l < r) {
18.             int mid = (l + r) >> 1;
19.             if(check(mid, k)) r = mid;
20.             else l = mid + 1;
21.         }
22.         return l;
23.     }
24.     int takeCharacters(string s, int k) {
25.         n = s.size();
26.         for(int i = 1; i <= n; i ++ ) {
27.             prea[i] = prea[i - 1] + (s[i  - 1] == 'a' ? 1 : 0);
28.             preb[i] = preb[i - 1] + (s[i  - 1] == 'b' ? 1 : 0);
29.             prec[i] = prec[i - 1] + (s[i  - 1] == 'c' ? 1 : 0);
30.         }
31.         for(int i = n; i >= 1; i -- ) {
32.             lasta[i] = lasta[i + 1] + (s[i - 1] == 'a' ? 1 : 0);
33.             lastb[i] = lastb[i + 1] + (s[i - 1] == 'b' ? 1 : 0);
34.             lastc[i] = lastc[i + 1] + (s[i - 1] == 'c' ? 1 : 0);
35.         }
36.         if(prea[n] < k || preb[n] < k || prec[n] < k) return -1;
37.         int l = 0, r = n;
38.         int res = find(0, n, k);
39.         return res;
40.     }
41. };

复制代码

---

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。