CodeForces 672B Different is Good

链接:http://codeforces.com/problemset/problem/672/B

本文链接:http://www.cnblogs.com/Ash-ly/p/5491176.html

题意:

　　输入第一行有一个数字N,紧接着第二行给你一个含有N个字符(全是小写)的字符串,为了使得这个字符串的所有连续的子串都不一样,让你给出最少的变化次数.

思路:

　　栗aba,连续的子串为a,b,a,ab,ba,含有相等的子串,最少改变一个字符就可以使得所有子串不一样(栗'a'-->'c').对于一个含有N个字符的字符串,暂且不用去考虑长度为2的子串,思考长度为1的子串,要想让这些长度为1的子串都不同,那么换种说法,就是至少改变几个字母使得所给字符串的每个字符都不相同,可以想到当N>26时显然是不可能的,对于当N<27时,要想子串都不同,那么这个字符串应该含有N个不同的字符.所以统计出现的字符个数cnt,用N-cnt即是所需的.

代码:

 1 #include <cstring>
 2 #include <cstdlib>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <string>
 6 
 7 int main(){
 8     //freopen("input.txt", "r", stdin);
 9     char s[100007] = {0};
10     int n;
11     scanf("%d%s", &n, s);
12     if(n > 26) printf("-1
");
13     else{
14         int aa[31] = {0}, cnt = 0;
15         for(int i = 0; i < n; i++)aa[s[i] - 'a']++;
16         for(int i = 0; i < 26; i++)if(aa[i])cnt++;
17         printf("%d
", n - cnt);
18     }
19     return 0;
20 }