题解 | #DNA序列#

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Scanner;

public class Main{
     public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner scanner = new Scanner(br);
        String str = scanner.nextLine();
        int length = scanner.nextInt();
        String result = getSubstringWithTheHighestGCRatio2(str,length);
        System.out.println(result);
    }

     /**
     * 滑动窗口求解
     */
    private static String getSubstringWithTheHighestGCRatio2(String str, int length) {
        if (str == null || str.length()==0 || length <= 0) return null;
        int left, right,max,count = 0,result = 0;
        // 创建窗口
        for (int i = 0; i < length; i++) {
            if (str.charAt(i) == 'C' || str.charAt(i) == 'G')
                count++;
        }
        max = count;
        left = 1;
        right = length;
        // 窗口的维护
        while (right < str.length()){
            if (str.charAt(left-1) == 'C' || str.charAt(left-1) == 'G')
                count--;
            if (str.charAt(right) == 'C' || str.charAt(right) == 'G')
                count++;
            if (count > max){
                max = count;
                result = left;
            }
            left++;right++;
        }
        return str.substring(result,result+length);

    }
    /**
     * 遍历求解
     */ 
    private static String getSubstringWithTheHighestGCRatio1(String str, int length) {
         if (str == null || str.length()==0 || length <= 0) return null;
        int max = 0;
        int result = 0;
        for (int i = 0; i < str.length()-length; i++) {
            int count = 0;
            String s = str.substring(i,i+length);
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == 'C' || s.charAt(j) == 'G')
                    count++;
            }
            if (max < count){
                max = count ;
                result = i;
            }

        }
        return str.substring(result,result+length);
    }
}