字节跳动2018后端开发编程题-字母交换

题目

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

我的思路

具体实现

	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)