解题思路

• 固定长度窗口问题：题目给定子串长度为固定的 k，在所有长度为 k 的子串中寻找 GC-Ratio 最高者。由于窗口长度一致，比较比例等价于比较窗口内 G/C 的计数。

• 算法选择：使用滑动窗口。

  • 先计算首个窗口 [0, k-1] 内 G 和 C 的个数 cnt。
  • 之后每次将窗口右移一位：若移出的字符是 G/C 则 cnt--，若新进入的是 G/C 则 cnt++。
  • 使用变量记录当前出现的最大 cnt 及其起始下标；若出现更大 cnt 则更新。若相等则保持原位置以满足“多个时输出第一个”的要求。

• 核心实现要点：

题目内容

一个 $DNA$ 序列由 $A/C/G/T$ 四个字母的排列组合组成。$G$ 和 $C$ 的比例(定义为 $GC-Ratio$ )是序列中 $G$ 和 $C$ 两个字母的总的出现次数除以总的字母数目(也就是序列长度)。在基因工程中，这个比例非常重要。因为高的 $GC-Ratio$ 可能是基因的起始点。

给定一个很长的 $DNA$ 序列，以及要求的最小子序列长度，研究人员经常会需要在其中找出 $GC-Ratio$ 最高的子序列。

$DNA$ 序列为 $ACGT$ 的子串有：$ACG,CG,CGT$ 等等，但是没有 $AGT,CT$ 等等

数据范围：字符串长度满足 $1≤n≤1000$，输入的字符串只包含 $A/C/G/T$ 字母

输入描述

输入一个 $string$ 型基因序列，和 $int$ 型子串的长度

输出描述

找出 $GC$ 比例最高的子串,如果有多个输出第一个的子串

样例1

输入

AACTGTGCACGACCTGA
5

输出

GCACG