Python-41：最小替换子串长度

问题描述

小F得到了一个特殊的字符串，这个字符串只包含字符A、S、D、F，其长度总是4的倍数。他的任务是通过尽可能少的替换，使得A、S、D、F这四个字符在字符串中出现的频次相等。求出实现这一条件的最小子串长度。

代码

from collections import Counter

def solution(input):

    # Please write your code here

    s = input

    n = len(s)

    assert n % 4 == 0

    cnt = Counter(s)

    if all(cnt[c] <= n // 4 for c in cnt):

        return 0

    l, r = 0, 0

    res = n

    while r < n:

        cnt[s[r]] -= 1

        r += 1

        while all(cnt[c] <= n // 4 for c in cnt) and l < r:

            res = min(res, r - l)

            cnt[s[l]] += 1

            l += 1

    return res

if __name__ == "__main__":

    #  You can add more test cases here

    print(solution("ADDF") == 1 )

    print(solution("ASAFASAFADDD") == 3)