首页 > 牛客编程巅峰赛第7场钻石王者组第一题
头像
六娃lw
编辑于 2020-12-09 10:25
+ 关注

牛客编程巅峰赛第7场钻石王者组第一题

来源:牛客网
牛牛现在有一个长度为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) 回帖
加载中...
话题 回帖

相关热帖

近期精华帖

热门推荐