题解 | #DNA序列#

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        char[] chars=str.toCharArray();
        int num=Integer.valueOf(br.readLine());
        // dp[i]表示i->i+num的子串中包含的GC数量，dp[i]=dp[i-1]-char[i-1]=GC?1+char[i+num-1]=GC?1
        int max=0,maxIndex=0;
        //计算0-num的GC数量
        for(int i=0;i<num;i++){
            if(chars[i]=='G'||chars[i]=='C'){
                max++;
            }
        }
        int last=max;
        //依次计算后续子串的GC数量
        for(int i=1;i<chars.length-num+1;i++){
            if(chars[i-1]=='G'||chars[i-1]=='C'){
                last--;
            }
            if(chars[i+num-1]=='G'||chars[i+num-1]=='C'){
                last++;
            }
            if(last>max){
                max=last;
                maxIndex=i;
            }
        }
        System.out.print(str.substring(maxIndex,maxIndex+num));
    }
}