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 allsubstrings 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 strings.

The second line contains the string s of lengthn 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.

2aaOutput
1Input
4kokoOutput
2Input
5muratOutput
0Note
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".
題目大意：
給你一個(gè)長度為N的由小寫字母組成的字符串，問你能否找到一種方案，使得這個(gè)字符串的所有子串都不相等。
如果有，輸出最少修改的字符個(gè)數(shù)，否則輸出-1.
思路:
對(duì)于一個(gè)字符串來講，所有子串必然包括每個(gè)位子的字符作為單個(gè)子串，那么其實(shí)問題就是讓你改變最少字符個(gè)數(shù)，使得每個(gè)字符都不同。
那么接下來找好姿勢(shì)隨便貪心即可。
Ac代碼：
#include<stdio.h>#include<string.h>using namespace std;char a[100070];int vis[300];int main(){    int n;    while(~scanf("%d",&n))    {        memset(vis,0,sizeof(vis));        scanf("%s",a);        int ok=1;        int output=0;        for(int i=0;i<n;i++)        {            vis[a[i]]++;        }        for(int i=0;i<n;i++)        {            if(vis[a[i]]>1)            {                int flag=0;                for(int j='a';j<='z';j++)                {                    if(vis[j]==0)                    {                        output++;                        flag=1;                        vis[j]=1;                        vis[a[i]]--;                        break;                    }                }                if(flag==0)ok=0;            }        }        for(int i=0;i<n;i++)if(vis[a[i]]>1)ok=0;        if(ok==0)printf("-1/n");        else        printf("%d/n",output);    }}