【模拟】重复字符串【蓝桥杯】

题目

重复字符串 - 蓝桥云课

---

问题描述

如果一个字符串 $S$ 恰好可以由某个字符串重复 $K$ 次得到，我们就称 $S$ 是 $K$ 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 $3$ 次得到，所以 abcabcabc 是 $3$ 次重复字符串。

同理 aaaaaa 既是 $2$ 次重复字符串、又是 $3$ 次重复字符串和 $6$ 次重复字符串。

现在给定一个字符串 $S$，请你计算最少要修改其中几个字符，可以使 $S$ 变为一个 $K$ 次字符串？

输入格式

输入第一行包含一个整数 $K$。

第二行包含一个只含小写字母的字符串 $S$。

其中，$1 \le K \le 10^5, 1 \le |S| \le 10^5$。其中 $|S|$ 表示 $S$ 的 长度。

输出格式

输出一个整数代表答案。如果 $S$ 无法修改成 $K$ 次重复字符串，输出 $−1$。

样例输入

2
aabbaa

样例输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存：128M

解题

方法一：模拟

思路

首先判断 $S$ 的长度是否是 $K$ 的整数倍，如果不是的话 $S$ 肯定无法修改成 $K$ 次重复字符串，输出 $−1$。

把 $S$ 分成长度为 $\frac{S}{K}$ 的 $K$ 段，然后枚举每一段的第 $i$ 个字符，统计出在该位置出现次数最多的字符出现的次数 $mx$，那么 $k-mx$ 就是该位置要修改的字符数量，把所有位置要修改的字符数量累和起来就得到了答案。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        int k = (int) in.nval;
        char[] s = br.readLine().toCharArray();
        int n = s.length;
        if (n % k != 0) {
            System.out.println(-1);
            return;
        }
        int partLen = n / k;
        int[] cnts = new int[26];
        int ans = 0;
        for (int i = 0; i < partLen; ++i) {
            int mx = 0;
            Arrays.fill(cnts, 0);
            for (int j = i; j < n; j += (partLen)) {
                if (++cnts[s[j] - 'a'] >= mx) mx = cnts[s[j]- 'a'];
            } 
            ans += k - mx;
        }
        System.out.println(ans);
    }
}