牛客 牛牛的独特子序列（双指针/二分查找）

文章目录

• • 1. 题目
  • 2. 解题
  • • 2.1 双指针
    • 2.2 二分查找

1. 题目

链接：https://ac.nowcoder.com/acm/contest/9752/B
来源：牛客网

牛牛现在有一个长度为len只包含小写字母‘a’-'z’的字符串x，他现在想要一个特殊的子序列，
这个子序列的长度为3*n（n为非负整数），
子序列的第[1,n]个字母全部为‘a’，
子序列的[n+1,2*n]个字母全部为‘b’，
子序列的[2*n+1,3*n]个字母全部为‘c’，
牛牛想知道最长的符合条件的独特子序列的长度是多少。

示例1 输入 "cbacb" 返回值 0 说明 没有符合条件的非空子序列，所以输出0示例2 输入 "abaabbcccc" 返回值 6 说明 最长的符合条件的子序列为"aabbcc"，所以输出6

2. 解题

2.1 双指针

class Solution { public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* * @param x string字符串 * @return int整型*/// typedef pair<int,int> pii;int Maximumlength(string x) {// write code herestring s;for(auto c : x)if(c=='a' || c=='b' || c=='c')s += c; //只需要abc字符int n = s.size();if(n < 3) return 0;vector<int> numa(n+1, 0), numb(n+1, 0), numc(n+1, 0);//前缀和个数for(int i = 1; i <= n; i++){if(s[i-1] == 'a'){numa[i] = numa[i-1] + 1;numb[i] = numb[i-1];numc[i] = numc[i-1];}else if(s[i-1] == 'b'){numa[i] = numa[i-1];numb[i] = numb[i-1]+1;numc[i] = numc[i-1];}else{numa[i] = numa[i-1];numb[i] = numb[i-1];numc[i] = numc[i-1]+1;}}int ans = 0, a = 0, b= 0, c= 0;int i = 1, j = n;// 贪心，让 a c，交替变多while(i <= j){int MIN = min(a,min(b,c));//数量最少的if(MIN == a){a = numa[i++];}else if(MIN == c){c = numc[n]-numc[--j];}elsebreak;b = numb[j]-numb[i-1];ans = max(ans, 3*min(a,min(b,c)));}return ans;} };

2.2 二分查找

通用解法

class Solution { public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* * @param x string字符串 * @return int整型*/// typedef pair<int,int> pii;int Maximumlength(string x) {// write code herestring s;for(auto c : x)if(c=='a' || c=='b' || c=='c')s += c;int n = s.size();if(n < 3) return 0;int l = 0, r = n/3, mid, ans = 0;while(l <= r){mid = (l+r)/2;if(ok(s, mid)){ans = mid*3;l = mid+1;}elser = mid-1;}return ans;}bool ok(string& s, int n){int a = 0, b =0, c = 0;for(int i = 0; i < s.size(); ++i){if(a < n){if(s[i] == 'a')a++;}else if(b < n){if(s[i]== 'b')b++;}else{if(s[i] == 'c')c++;}}return c >= n;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的牛客 牛牛的独特子序列（双指针/二分查找）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。