来源：牛客网
牛牛现在有一个长度为len只包含小写字母‘a’-'z'的字符串x，他现在想要一个特殊的子序列，这个子序列的长度为3*n（n为非负整数），子序列的第[1,n]个字母全部为‘a’，子序列的[n+1,2*n]个字母全部为‘b’，子序列的[2*n+1,3*n]个字母全部为‘c’，牛牛想知道最长的符合条件的独特子序列的长度是多少。
牛牛现在有一个长度为len只包含小写字母‘a’-'z'的字符串x，他现在想要一个特殊的子序列，这个子序列的长度为3*n（n为非负整数），子序列的第[1,n]个字母全部为‘a’，子序列的[n+1,2*n]个字母全部为‘b’，子序列的[2*n+1,3*n]个字母全部为‘c’，牛牛想知道最长的符合条件的独特子序列的长度是多少。
// 二分法求最值。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param x string字符串
* @return int整型
*/
public int Maximumlength (String x) {
// write code here
char[] chars = x.toCharArray();
int len = chars.length;
StringBuilder sb = new StringBuilder();
int aCount = 0, bCount = 0, cCount = 0;
for(char ch: chars){
if(ch == 'a'){++aCount;sb.append(ch);}
else if(ch == 'b'){++bCount;sb.append(ch);}
else if(ch == 'c'){++cCount;sb.append(ch);}
}
chars = sb.toString().toCharArray();
len = sb.length();
int minCount = Math.min(Math.min(aCount, bCount), cCount);
int res = 0;
int l = 1; int r = minCount;
while(l < r){
int mid = l + ((r - l + 1) >> 1);
if(helper(chars, len, mid)){
l = mid;
}else{
r = mid - 1;
}
}
return helper(chars, len, l) ? l * 3 : 0;
}
private static boolean helper(char[] chars, int len, int i){
int ac = 0, bc = 0, cc = 0;
int j = 0;
for(; j < len; ++j){
char ch = chars[j];
if(ch == 'a'){
if(++ac == i){
++j;
break;
}
}
}
for(; j < len; ++j){
char ch = chars[j];
if(ch == 'b'){
if(++bc == i){
++j;
break;
}
}
}
for(; j < len; ++j){
char ch = chars[j];
if(ch == 'c'){
if(++cc == i){
++j;
break;
}
}
}
if(cc == i){return true;}
else{return false;}
}
}
全部评论
(0) 回帖