题解 | #DNA序列# 动态规划

import java.io.IOException;
import java.util.*;

/**
 * @author eagle2020java.util.LinkedHashSet1/9/29
 */
public class Main {
    //a@c
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();//读取当前行字符串
            int subLen = sc.nextInt();
            int len = s.length();
            if (len <= subLen) {//长度较短，不再往下走
                System.out.println(s);
                return;
            }
            int[] dp = new int[len + 1];
            for(int i = 1; i <= subLen; i++){//先遍历前subLen个字符串，记录CG个数
                if(c_g(s.charAt(i - 1))){
                    dp[i] = dp[i - 1] + 1;//如果当前字符是c g，就比前边的字符串片段多一个cg个数
                }else{
                    dp[i] = dp[i - 1];
                }
            }
            //假设刚开始的subLen个字符就是返回值
            int endIndex = subLen - 1;
            int maxCGLen = dp[subLen];//cg个数
            // 滑动窗口的思想，窗口长度为subLen，每次向右滑动一个，比较坐标i对应新入的字符和刚刚被略过的i- subLen对应的字符，新vs旧
            for(int i = subLen + 1; i <= len; i++){
                char c = s.charAt(i - 1);
                char csubLen = s.charAt(i - 1 - subLen);//旧字符
                //如果新字符和旧字符都是cg或者都不是cg,则不用处理
                if(c_g(c) ^ c_g(csubLen)){//异或运算，新字符和旧字符其中只有一个是cg
                    if(c_g(c)){ //如果新字符是cg,则新的滑动窗口对应的cg个数要加一
                        dp[i] = dp[i - 1] + 1;

                    }else {//否则少了一个cg,要减一
                        dp[i] = dp[i - 1] - 1;
                    }
                }else {//新字符和旧字符都是cg或者都不是cg
                    dp[i] = dp[i - 1];
                }
                //
                if(dp[i] > maxCGLen){
                    endIndex = i - 1;
                    maxCGLen = dp[i];
                }
            }
            System.out.println(new StringBuilder(s).substring(endIndex + 1- subLen, endIndex + 1));
        }
    }
    static boolean c_g(char c){
        return c == 'C' || c == 'G';
    }

}