【蓝桥杯】历届真题 重复字符串（省赛）Java

【资源限制】

内存限制：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 的
长度。

【前言】

        这道题在解的过程中发现了点问题，可能是测试用例的问题。

        因题中所说的是：如果s无法修改成k次重复字符串，输出-1，所以在最开始判断一下。

        if(len%k != 0){
            System.out.println(-1);
            return;
        }

        但加上上述代码后，只有90，最后一个测试用例拿不到分。

        因此官方数据错误，不完整的循环节也输出了答案，例如 abcde 当 k 取 3 的时候，可以修改为 abc，这是不符合题意的。
        如果非要过官方OJ，修改代码 -1 输出的条件为 length < k，且将字符串长度截断为abc即可。

【思路及分析】

        若字母序列为aab，要让它们一样，只需要将b改为a即可，即变化成aaa。

        由此可知，只需要找到这一列中哪个字母数最多的，那么剩下的字母都改为该字母是操作最少的。

        因此，我们只需要统计每一个字母序列中出现次数最多的字母出现的次数即可，记为max，那么用该列的长度k减去max，即为该列需要更改的次数。

【代码】

import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		String str = sc.next();
		char[] c = str.toCharArray();
		
		int len = str.length();
		if(len%k != 0){
			System.out.println(-1);
			return;
		}
		int sum = 0;
		int max = 0;
		int temp = 0;
		int[] arr = new int[26];
		
		for(int i=0; i<arr.length; i++){
			arr[i] = 0;
		}
		
		for(int i=0; i<len/k; i++){
			for(int j=i; j<len; j+=(len/k)){
				temp = (int)(c[j]-'a');
				arr[temp]++;
			}
			for(int m=0; m<arr.length; m++){
				if(arr[m]>max){
					max = arr[m];
				}
			}
			sum += (k-max);
			max = 0;
			for(int n = 0; n<arr.length; n++){
				arr[n]=0;
			}
		}
		System.out.println(sum);
	}
}