[编程题]字母交换

热度指数：2580时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M

链接：https://www.nowcoder.com/questionTerminal/43488319efef4edabada3ca481068762

来源：牛客网

【编码题】字符串S由小写字母构成，长度为n。定义一种操作，每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？

输入描述: 第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)

输出描述: 一个非负整数，表示操作之后，连续最长的相同字母数量。
示例1

输入 abcbaa 2

输出 2

说明

使2个字母a连续出现，至少需要3次操作。即把第1个位置上的a移动到第4个位置。所以在至多操作2次的情况下，最多只能使2个b或2个a连续出现。

First Try

2020-10-07

终于成功搞定，这个bug真是找了几个小时，一直没想明白问题出在哪里。其实就是直接计算dp(0, n-1)，很神奇的并没有遍历所有i，j的可能，导致cache中出现空白。而在计算max的时候，没被计算的反而存在最大连续字符串的可能。

比如'aaabba 1'的计算中，用failed try只能得到2，但其实默认的a就有3的长度了。所以对所有i，j的选择，都计算了一遍dp函数，反正递归运算中存在缓存，最终只是O(n^2)的复杂度。

这题目如果考虑解析解正面破解真是很头疼，散布在坐标轴的点，如何移动最少次数让更多点混合一起？往哪个方向移动最合适，中间点还是平均点？根本无从下手。

没想到用暴力模拟法动态规划竟然能够解决这个问题，这就是算法的奇妙之处。对于每个字母，考虑移动在一起所需要的次数。但由于次数有限，因此要看在m个次数中所能聚拢的最多元素。暴力法直接计算了所有可能，比如对于i和j位置中的所有字母a，全都汇合一起需要的次数是dp[i][j], 然后暴力筛选所有i/j组合，找到符合m次移动数量内最大可汇聚的字母数量。所有字母也在来一波，这么三轮暴力下来就搞定了。

而对于dp[i][j], 动态规划的转移方程为 dp[i][j] = dp[i + 1][j - 1] + (arr[j] - arr[i] - 1 ) - ( j - i - 1); 如果i = j - 1，则dp[i][j] = j - i - 1；如果i = j，则dp[i][j] = 0.

在这个转移方程中，每次都缩小需要考虑的范围。对于i,j距离，其中间的[i+1, j-1]已经确定，那么i, j只需要往中间这一坨走过去就行了，这一坨的大小是j-i-1.

这个动态规划确实巧妙，看题解才了解到思路，不然这种看起来简单的题目真是无从下手。

import collections 

txt, m = input().split()
m = int(m)
col = collections.defaultdict(list)
for idx, c in enumerate(txt):
    col[c].append(idx)
    
"""
"a": [2, 5, 10, 11]
"b": [3, 4, 7], 需要2次。 dp[1][1] = 0, arr[2] - arr[0] -1 = 3, 2 - 0 - 1 = 1
dp[i][j]  = dp[i + 1][j - 1] + (arr[j] - arr[i] - 1) - (j - i - 1)
dp[i][i] = 0, dp[i][i + 1] = arr[i + 1] - arr[i]
"""

def dp(i, j, arr, cache):
    if cache[i][j] != "":
        return cache[i][j]
    
    if i == j:
        t = 0 
    elif j == i + 1:
        t = arr[j] - arr[i] - 1 # 贴近，而不是变成一样
    else:
        # 对于i,j,中间的[i+1, j-1]已经确定，那么i, j只需要往中间这一坨走过去就行了，这一坨的大小是j-i-1
        # 算恰里挺头痛，无非就是+1和-1的问题
        t = dp(i + 1, j - 1, arr, cache) + (arr[j] - arr[i] - 1) - (j - i - 1)    
    cache[i][j] = t 
    return cache[i][j]

maxv = 0 
for k, vals in col.items():
    cache = [[""] * len(vals) for _ in range(len(vals))]
    # dp(0, len(vals) - 1, vals, cache)
    # print("k", k, vals, cache)
    maxgap = 0 
    for i in range(len(vals)):
        for j in range(i, len(vals)):
            if dp(i, j, vals, cache) != "" and cache[i][j] <= m:
                maxgap = max(maxgap, j - i + 1)
    # print(k, maxgap)
    maxv = max(maxv, maxgap)
print(maxv)

Failed Try

2020-10-07

还不知道哪里出了问题。。。

经过测试，发现是dp[i][j]的计算并没有遍历到所有可能，导致不需要计算到的地方反而出现了较大的原始值，于是才在最后的测试案例中失败。具体参考first try中的分析和新解法。

import collections 

txt, m = input().split()
m = int(m)
col = collections.defaultdict(list)
for idx, c in enumerate(txt):
    col[c].append(idx)
    
"""
"a": [2, 5, 10, 11]
"b": [3, 4, 7], 需要2次。 dp[1][1] = 0, arr[2] - arr[0] -1 = 3, 2 - 0 - 1 = 1
dp[i][j]  = dp[i + 1][j - 1] + (arr[j] - arr[i] - 1) - (j - i - 1)
dp[i][i] = 0, dp[i][i + 1] = arr[i + 1] - arr[i]
"""

def dp(i, j, arr, cache):
    if cache[i][j] != "":
        return cache[i][j]
    if i == j:
        t = 0 
    elif j == i + 1:
        t = arr[j] - arr[i] - 1 # 贴近，而不是变成一样
    else:
        # 对于i,j,中间的[i+1, j-1]已经确定，那么i, j只需要往中间这一坨走过去就行了，这一坨的大小是j-i-1
        # 算恰里挺头痛，无非就是+1和-1的问题
        t = dp(i + 1, j - 1, arr, cache) + (arr[j] - arr[i] - 1) - (j - i - 1)    
    cache[i][j] = t 
    return cache[i][j]

maxv = 0 
for k, vals in col.items():
    cache = [[""] * len(vals) for _ in range(len(vals))]
    dp(0, len(vals) - 1, vals, cache)
    maxgap = 0 
    for i in range(len(vals)):
        for j in range(len(vals)):
            if cache[i][j] != "" and cache[i][j] <= m:
                maxgap = max(maxgap, j - i + 1)
    # print(k, maxgap)
    maxv = max(maxv, maxgap)
print(maxv)

答案错误:您提交的程序没有通过所有的测试用例
case通过率为90.00%

用例:
hkdbqojqvxlfulshrhpysezhlyzolb 20

对应输出应该为:

3

你的输出为:

2