题目分析

1. 题目给出我们一个由A/G/C/T四种字母组成的字符串，并且给出了一个目标子串的固定长度值
2. 题目希望我们在给定长度下锁定一个子串中，输出从左到右数G和C出现的比率最高的第一个给定长度的的子串

方法一：暴力截取子串并计数

• 实现思路

  • 我们直接用python切片的方式，遍历给出的字符串来获得一个个目标子串

  • 然后对目标字串进行G和C的计数

  • 如果G和C的数量占比高，则更新可能的输出结果

  • 直到遍历结束为止，输出第一个G和C含量最高的子串

def solution(s, k):
    if k >= len(s):                                # 处理特殊情况
        print(s)
        return
    mx = 0
    res = ""
    for i in range(len(s)-k):                      # 遍历字符串，找到子串的起点
        sub = s[i:i+k]                             # 获得子串
        count = sub.count('C') + sub.count('G')    # 计算CG的含量
        if count > mx:                             # 根据CG含量更新最大值
            mx = count
            res = sub
    print(res)
    return

while True:
    try:
        s = input()
        k = int(input())
        solution(s, k)
    except:
        break

复杂度分析

• 时间复杂度：$O(k(n-k))O(k(n-k))$，其中n是给出字符串的长度，k是截取的子字符串长度。由于只遍历一次字符串，且遍历的起点只有n-k个，所以代价为$O(n-k)O(n-k)$，但是对于每个子串都需要遍历一轮数出所有的G和C的数量，因此最终代价为$O(k(n-k))O(k(n-k))$
• 空间复杂度：$O(k)O(k)$，每轮存储子串长度的字符串变量空间开销

方法二：滑动窗口优化计数

• 实现思路
  • 在方法一的基础上，我们在字串的G和C含量统计上进行优化
  • 我们通过控制窗口访问的元素来调整计数结果
  • 如果左侧的元素退出窗口，右侧有新的元素进入窗口，判断是否是C或G来调整计数的结果
  • 这样优化了内层对于子串的遍历开销

def solution(s, k):
    if k >= len(s):                                # 处理特殊情况
        print(s)
        return
    sub = s[:k]
    cur = mx = sub.count('C') + sub.count('G')
    res = sub
    for i in range(1, len(s)-k):                          # 遍历字符串，找到子串的起点
        sub = s[i:i+k]
        if s[i - 1] == 'C' or s[i - 1] == 'G':            # 如果左侧刚刚退出一个字符C或G，则计数器-1
            cur -= 1
        if s[i + k - 1] == 'C' or s[i + k - 1] == 'G':    # 如果右侧刚刚进入一个字符C或G，则计数器+1
            cur += 1
        # print(sub, cur, sub.count('G')+sub.count('C'))
        if cur > mx:                                      # 是否要更新新的结果
            res = sub
            mx = cur
    print(res)
    return

while True:
    try:
        s = input()
        k = int(input())
        solution(s, k)
    except:
        break

复杂度分析

• 时间复杂度：$O(n)O(n)$，由于首先初始化cur变量时候，一次子串的遍历计数时间为$O(k)O(k)$，然后在循环过程中遍历的代价又是$O(n-k)O(n-k)$，因此最终的时间代价为$O(n)O(n)$
• 空间复杂度：$O(k)O(k)$，每轮存储子串长度的字符串变量空间开销