M30942: 最大连续答案

sliding window, http://cs101.openjudge.cn/practice/30942/

给定一个长度不超过20000的由'T'或'F'构成的字符串，允许修改字符最多k次（将'T'改成'F'或将'F'改成'T')，问能得到的最长的连续相同字符字串长度是多少。
输入
第1行，一个由'T'或'F'构成的字符串第2行：整数k (0 <= k <= 第1行字符串长度）
输出
答案
样例输入
TTFF
2
样例输出
4

思路：滑动窗口。分别将 'T' 和 'F' 视为目标字符，用双指针维护窗口内最多允许 k 个非目标字符。每一次移动右指针扩大窗口，若窗口内非目标字符超过 k 则移动左指针收缩。记录窗口最大长度。

python

def solve():
    s = sys.stdin.readline().strip()
    k = int(sys.stdin.readline())
    ans = 0
    for target in ('T', 'F'):
        l = cnt = 0
        for r in range(len(s)):
            if s[r] != target:
                cnt += 1
            while cnt > k:
                if s[l] != target:
                    cnt -= 1
                l += 1
            ans = max(ans, r - l + 1)
    print(ans)

if __name__ == "__main__":
    import sys
    solve()

M30942: 最大连续答案 ​

M30942: 最大连续答案