题解 | #DNA序列#

import sys
str1 = sys.stdin.readline().strip()
n = int(sys.stdin.readline().strip())

left, right = 0, n-1
ans = str1[left:right + 1]
count = ans.count('C') + ans.count('G')
while right  <= len(str1) - 1:
    if str1[right] != 'C' and str1[right] != 'G':
        right += 1
    left = right - n + 1
    temp = str1[left:right+1]
    if temp.count('C') + temp.count('G') > count:
        ans = temp
        count = temp.count('C') + temp.count('G')
    right += 1

print(ans)

首先想到的是从左至右依次找出长度为n的子串，如果CG个数比原来的大，就替换成新的。

我做了点剪枝操作：当我们计算完一个字符串后，会将原子串的位置向右平移一位的得到对应的新子串，它们中间字符保持不变，只有首位和末尾发生了变化，如果新的子字符串的末尾不是'C'或者'G'，那么CG比例比起前一个子串，要么保持不变（原来子字符串的首位不是'C'或'G'），而且不是第一个有此CG比例的，要么减少（原来子字符串的首位是'C'或'G'），所以无需计算比较。因此，right指针不是每次都往右移一位，而是向右移到'C'或者'G'的位置，然后再计算新的CG比例，与之前的结果比较。