2020年蓝桥杯Python大学组G题：如何高效处理重复字符串问题？

本文共计482个文字，预计阅读时间需要2分钟。

在在线评测中，使用 Ideas 首先把字符串分割成 k 个部分，然后逐个比较每个部分，计算出出现次数最多的字母，并使用 k 减去这个出现次数最多的字母的数量，找到需要修改的位置。下面是 Python 代码实现：

pythonfrom collections import Counter

def find_to_change(string, k): # 将字符串分割成 k 个部分 parts=[string[i:i+k] for i in range(0, len(string), k)]

# 统计每个部分中字母出现的次数 counts=[Counter(part) for part in parts]

# 找出每个部分中出现次数最多的字母 most_common_chars=[max(count, key=count.get) for count in counts]

# 计算每个部分需要修改的字母数量 changes_needed=[k - counts[i][most_common_chars[i]] for i in range(len(parts))]

# 找到需要修改的次数最多的位置 max_changes=max(changes_needed) positions_to_change=[i for i, change in enumerate(changes_needed) if change==max_changes]

# 返回需要修改的位置 return positions_to_change

示例string=Ideask=3positions=find_to_change(string, k)print(positions)

这段代码会输出需要修改的位置索引，例如，对于字符串 Ideas 和 k=3，可能会输出 `[0]` 或 `[1]` 或 `[2]`，这取决于哪个部分有最多的重复字母。

​​在线评测​​

Ideas

首先把字符串划分成 k 份，然后每份逐位对比，计算出现次数最多的字母，然后用 k 减去出现次数就是要修改的位置。

Code

Python

from collections import Counter


if __name__ == '__main__':
ans = 0
k = int(input())
string = input()
n = len(string)
if n < k:
print(-1)
else:
string_list = [string[i: i + n // k] for i in range(0, n, n // k)]
for i in range(n // k):
cnt = Counter()
for j in range(len(string_list)):
cnt[string_list[j][i]] += 1
ans += k - cnt.most_common(1)[0][1]
print(ans)