Codeforces Round #352 (Div. 2) B
2 seconds
256 megabytes
standard input
standard output
A wise man told Kerem "Different is good" once, so Kerem wants all things in his life to be different.
Kerem recently got a string s consisting of lowercase English letters. Since Kerem likes it when things are different, he wants all substrings of his string s to be distinct. Substring is a string formed by some number of consecutive characters of the string. For example, string "aba" has substrings "" (empty substring), "a", "b", "a", "ab", "ba", "aba".
If string s has at least two equal substrings then Kerem will change characters at some positions to some other lowercase English letters. Changing characters is a very tiring job, so Kerem want to perform as few changes as possible.
Your task is to find the minimum number of changes needed to make all the substrings of the given string distinct, or determine that it is impossible.
The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the length of the string s.
The second line contains the string s of length n consisting of only lowercase English letters.
If it's impossible to change the string s such that all its substring are distinct print -1. Otherwise print the minimum required number of changes.
2
aa
1
4
koko
2
5
murat
0
In the first sample one of the possible solutions is to change the first character to 'b'.
In the second sample, one may change the first character to 'a' and second character to 'b', so the string becomes "abko".
题意:长度为n的小写字母字符, 要求分解之后 不能有相同的字符串 ,问需要更改多少个字符,当无法实现时输出-1
题解:分析可知 当n>26 必然存在相同字符 输出-1
n<=26 处理 计算重复的数量 输出
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<stack>
#define ll __int64
#define pi acos(-1.0)
using namespace std;
char a[];
map<char,int>mp;
int n;
int main()
{
scanf("%d",&n);
mp.clear();
getchar();
for(int i=;i<=n;i++)
{
scanf("%c",&a[i]);
mp[a[i]]++;
}
if(n>)
{
cout<<"-1"<<endl;
return ;
}
int ans=;
for(int i='a';i<='z';i++)
{
if(mp[i]>)
{
ans=ans+mp[i]-;
}
}
cout<<ans<<endl;
return ;
}
最新文章
- UITableView详细注释
- Exception&;Error
- JDK源码解读之toUnsignedString
- 0525Sprint回顾
- sql的 group by 分组;linq的 group by 分组
- jsp内置对象和el表达式
- Spiral Matrix II
- 彻底卸载网易UU网游加速器的方法
- (转载)利用burp suite截断上传拿shell
- Sysrq 诊断系统故障 与 gdb 调试core dump
- 转:测试用书(出处:cnblog--liangshi)
- 替换Gravatar头像默认服务器
- SQL 注入~MySQL专题
- mysql本地安装
- /WebRoot/WEB-INF/web.xml
- Javascript经典算法学习1:产生随机数组的辅助类
- readlink 命令
- 阿里云服务器如何设置IPV6通过appstore的审核
- 前端:jQuery笔记
- centos7 添加用户并授权root权限