题目

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

我的思路

实际在做题的时候主要分为三部分
1.按序接受输入的参数
2.对于字母的处理
由于是只有小写字母，而且后面解决问题时，只涉及到同类字母的出现位置，所以我使用了一个dict来进行存储字母以及相应的位置信息（键 为字母，值为 出现位置 的list)
3.对于整理好同类字母以及其对应的位置信息后，寻找递推式，使用动态规划dp
根据实例，可以得出 同一个字母的位置列表（假定为arr)中其一些规律，i，和j为数组索引,dp[i][j]表示使得arr[i]和arr[j]相邻的最少交换次数
(1) i==j 是，表示的是一个字符，这个时候不需要交换就能相邻，dp[i][j]=0
(2)两两相邻的元素arr[i],arr[j]，要在实际的S中，使得他们相邻，要交换的次数为arr[j]-arr[i]-(j-i)
(3)不相邻的元素arr[i],arr[j],那么dp[i+1][j-1]+arr[j]-arr[i]-(j-i)
也就是说，往中间靠拢，先得到使得中间是连续字符要交换的次数+当前次数。
为什么（2）（3）中，都要减去（j-i)呢，这个得到的是中间该字母出现的次数，我们默认中间是靠拢了的，所以要减去中间该字母出现的次数

具体实现 




	import sys





	line=sys.stdin.readline().strip()





	s,n=line.split()





	n=int(n)





	se=set(s)





	





	res=1





	sdict={}





	for i in se:





	sdict[i]=[]





	for j in range(len(s)):





	sdict[s[j]].append(j)





	





	forcinse:





	dp=[]*len(sdict[c])





	foriinrange(len(sdict[c])):





	dp.append([0]*len(sdict[c]))





	





	#for i in range(len(sdict[c])):





	#dp[i][i]=0





	





	foriinrange(0,len(sdict[c])-1):





	#print(i)





	forjinrange(i+1,len(sdict[c])):





	rr=sdict[c][j]-sdict[c][i]-(j-i)





	





	ifi+1!=j:





	rr+=dp[i+1][j-1]





	





	dp[i][j]=rr





	ifdp[i][j]<=n:





	#print('change',i,j,dp[i][j],res,j-i+1)





	res=max(res,j-i+1)





	





	print(res)

另外对于解题思路部分，中的（3），我花了很多时间
（1）一开始使用的是穷举法
（2）对于dp,我开始的时候用的是一维数组存储dp,我以为只要解决dp[0][j]即可，但是题目的解也有可能出现在 dp[i][j]中
（3）在python3中声明一个大小确定的二维数组确实不太elegant，难怪看到解题的回答中，都没有使用python的
（4）后面测试通过率只有85%,实在不太明白，我看了下其他用c++实现的解法，是差不多的思路