试题 历届真题 重复字符串【第十一届】【决赛】【Python】
一、题目来源：第十一届蓝桥杯决赛——重复字符串
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
【问题描述】
如果一个字符串 S 恰好可以由某个字符串重复 K 次得到，我们就称 S 是
K 次重复字符串。例如 “abcabcabc” 可以看作是 “abc” 重复3次得到，所以
“abcabcabc"是3次重复字符串。
同理 “aaaaaa” 既是2次重复字符串、又是3次重复字符串和6次重复字
符串。
现在给定 一个字符串S，请你计算最少要修改其中几个字符，可以使 S 变
为一个 K 次字符串?
【输入格式】
输入第一行包含一个整数 K。
第二行包含一个只含小写字母的字符串 S 。
【输出格式】
输出一个整数代表答案。如果 S 无法修改成K次重复字符串，输出-1。
【样例输入】
2
aabbaa
【样例输出】
2
【评测用例规模与约定】
对于所有测评用例，1≤K≤100000，1≤|S|≤100000。其中 |S| 表示 S 长度。
二、解题
1、思路
1、首先 S 可以重复 K 次，那么len(S)%K == 0，但这有坑！
2、将 S 分成 K 组，每组 d=len(S)//K个字符，因此可以建立一个二维数组res[K][d]。每行表示一组重复的子字符串。
3、统计每列的出现字符次数最多的字符的次数，把出现次数少于出现次数最多的字符变成该字符，那么这一列改变字符次数最少。
4、累计K组应该改变字符的次数，即得到最终的改变次数。
5、如果程序中使用了下列代码，则只能得到90分。感谢这篇博客的提醒。
if len(S)%K == 0: print(-1)
2、举例
K = 5
S = asdadsfsdavklsdnkvls
第k组 0 1 2 3 0 a s d a 1 d s f s 2 d a v k 3 l s d n 4 k v l s 最多次数字符 : 次数 d:2 s:3 d:2 s:2 需要改动次数 : 3 2 3 3 则最后需要更改字符的次数为：3+2+3+3=11
3、代码
K = int(input()) # 字符串重复的次数
S = input() # 字符串
d = len(S)//K # 重复节的长度
index = 0 # 指示字符串S的下标
res = [{} for _ in range(d)] # 用于记录每列各个字符出现的次数
ans = 0 # 记录更改的次数
for i in range(d):
for j in range(K):
temp = index+j*d # S 中处于同一列的字符下标
# 统计各个字符出现的次数
if S[temp] not in res[i]:
res[i][S[temp]] = 1
else:
res[i][S[temp]] +=1
index+=1
ans += K - max(res[i].values()) # 每列需要更改得次数
# 如果加上此段代码，只能得90分
# if len(S)%K!=0:
# print(-1)
# else:
print(ans)