题解 | #字母交换#

def cnt(vec, m):
    # vec: 当前字母的所有位置列表 (vec存储了某一个字母出现在字符串中的位置)
    # m:   允许的最大交换次数
    n = len(vec)  # n 是这个字母在字符串中出现的次数
    
    # 初始化一个二维dp数组，dp[i][j]表示从位置i到位置j所有字符排列成连续的最小交换代价
    dp = [[0] * n for _ in range(n)]
    
    # 初始化相邻两个位置之间的交换代价。
    # abs(vec[i + 1] - vec[i]) 是位置差，减1是为了计算需要的交换次数。
    for i in range(n - 1):
        dp[i][i + 1] = abs(vec[i + 1] - vec[i]) - 1

    # 通过动态规划计算更长区间的交换代价
    for j in range(2, n):
        for i in range(n - j):
            row, col = i, i + j
            # dp[row][col] 是从 vec[row] 到 vec[col] 的交换代价
            dp[row][col] = dp[row + 1][col - 1] + abs(vec[col] - vec[row]) - j

    max_length = 0  # 用于存储当前字母的最大连续子串长度
    # 遍历所有区间，找到可以通过最多m次交换形成的最大连续子串
    for i in range(n):
        for j in range(i, n):
            if dp[i][j] <= m:  # 如果从位置i到j的代价小于等于m
                max_length = max(max_length, j - i + 1)  # 更新最大长度

    return max_length  # 返回该字母下的最大连续子串长度

def main():
    # 输入
    str_input, m = input().split(' ')  # 输入字符串和交换次数
    m = int(m)  # 转换交换次数为整数
    
    # vec 存储每个字母出现的位置，vec[0] 对应'a'，vec[1] 对应'b'，以此类推
    vec = [[] for _ in range(26)]

    # 遍历字符串，记录每个字母在字符串中的出现位置
    for i, char in enumerate(str_input):
        vec[ord(char) - ord('a')].append(i)

    max_value = 0  # 用于存储所有字母中能达到的最大连续子串长度
    # 对于每一个字母，计算其能够形成的最大连续子串长度
    for k in range(26):
        if vec[k]:  # 该字母存在于字符串中
            max_value = max(max_value, cnt(vec[k], m))  # 计算并更新最大值

    print(max_value)  # 输出最终结果

if __name__ == "__main__":
    main()